Efficient Learning on Large Graphs using a Densifying Regularity Lemma
Authors: Jonathan Kouchly
Ben Finkelshtein
Michael M. Bronstein
Ron Levie
Venue: ICLR 2026 Poster (2026)
Keywords: regularity lemma
graphon
graph condensation
directed graphs
Primary area: learning on graphs and other geometries & topologies
TL;DR: We introduce a low-rank graph factorization, leading to an architecture with time and space complexity linear in the number of nodes.

Abstract: Learning on large graphs presents significant challenges, with traditional Message Passing Neural Networks suffering from computational and memory costs scaling linearly with the number of edges. We introduce the Intersecting Block Graph (IBG), a low-rank factorization of large directed graphs based on combinations of intersecting bipartite components, each consisting of a pair of communities, for source and target nodes. By giving less weight to non-edges, we show how an IBG can efficiently approximate any graph, sparse or dense. Specifically, we prove a constructive version of the weak regularity lemma: for any chosen accuracy, every graph can be approximated by a dense IBG whose rank depends only on that accuracy. This improves over prior versions of the lemma, where the rank depended on the number of nodes for sparse graphs. Our method allows for efficient approximation of large graphs that are both directed and sparse, a crucial capability for many real-world applications. We then introduce a graph neural network architecture operating on the IBG representation of the graph and demonstrating competitive performance on node classification, spatio-temporal graph analysis, and knowledge graph completion, while having memory and computational complexity linear in the number of nodes rather than edges.

Published as a conference paper at ICLR 2026
EFFICIENT LEARNING ON LARGE GRAPHS USING A DENSIFYING REGULARITY LEMMA
Jonathan Kouchly"
Ben Finkelshtein
Technion - Israel Institute of Technology
University of Oxford
Michael Bronstein
Ron Levie
University of Oxford AITHYRA
Technion Israel Institute of Technology
ABSTRACT
Learning on large graphs presents significant challenges, with traditional Message Passing Neural Networks suffering from computational and memory costs scaling linearly with the number of edges. We introduce the Intersecting Block Graph (IBG), a low-rank factorization of large directed graphs based on combinations of intersecting bipartite components, each consisting of a pair of communities, for source and target nodes. By giving less weight to non-edges, IBG can efficiently approximate any graph, sparse or dense. Specifically, we prove constructive version of the weak regularity lemma: for any chosen accuracy, every graph can be approximated by a dense IBG whose rank depends only on that accuracy. This improves over prior versions of the lemma, where the rank depended on the number of nodes for sparse graphs. Our method allows for efficient approximation of large graphs that are both directed and sparse, crucial capability for many real-world applications. We then introduce a graph neural network architecture operating on the IBG representation of the graph and demonstrating competitive performance on node classification, spatio-temport graph analysis, and knowledge graph completion, while having memory and computational complexity linear in the number of nodes rather than edges.
show how an
INTRODUCTION
Graphs are a powerful representation for structured data, with applications spanning social networks (Hamilton et al. 2017a Zeng et al., 2019). biological systems (Hamilton et al., (2077)), traffic modeling (Li et al. 2018), and knowledge graphs (Kok & Domingos, 2007). to name few. As graph sizes continue to grow in application, learning on such large-scale graphs presents computational and memory challenges. Traditional Message Passing Neural Networks (MPNNs), which form the backbone of most graph signal processing architectures, scale their computational and memory requirements linearly with the number of edges. This edge-dependence limits their scalability in some situations, e.g., when processing social networks that can typically have 10 10 nodes and 102 ~ 3 as many edges (Rossi et al. 2020).
Several strategies, called graph reduction methods, have been proposed to alleviate these challenges. These include graph sparsification, where smaller graph is randomly sampled from the large graph (Hamilton 2017a| ZZng al. [2019 Chen al. 20088;; graph condensation, where a new small graph is created (Jin et al., 2022; Wang et al. 2024 Zheng el al.) 2024), representing structures in the large graph; and graph coarsening, where sets of nodes are grouped into super nodes (Ying et al. 2018; Bianchi et al., 2020; Huang et al. [202I). However, with the exception of graph sparsification, graph reduction methods typically not address the problem of processing a graph that too large to fit at once in memory (e.g., on the GPU). For an extended related work, see Section A
Recently,FFikeessteen Recently, FFikelssheiin al. (2024a) proposed using low-rank approximation of the graph, called Intersecting Community Graph (ICG), instead of the graph itself, for processing the data. When training a model on the ICG representation, the computational complexity is reduced from linear in
Equal contribution. Correspondence to:

---

Published as a conference paper at ICLR 2026
0
100
200
50
100
150
(a) A directed graph.
(b) Approximating 3-IBG.
(c) The intersecting blocks of the 3-IBG.
Figure I: (a) Directed graph sampled from a stochastic block model (SBM); (b) The approximating 3-IBG, where source and target community pairs are represented by the same color; (e) Adjacency matrix of a graph sampled from the same SBM, with the 3-IBG overlaid on the adjacency matrix.
the number of edges (as in MPNNs) to linear in the number of nodes. However, ICG approximation quality deteriorates as graphs become sparser a significant limitation for domains like fraud detection, recommendation systems, and social networks where large graph size naturally results in sparse connectivity. Moreover, ICGs are restricted to undirected graphs, limiting their use in applications where edge directionality is essential, such as atmospheric flow in weather forecasting and causal reasoning in algorithms (Oskarsson et al. 2024 Smit al., 2025). In these settings, both empirical and theoretical work has shown that directionality is key and can significantly boost GNN performance and expressive power (Rossi et al. 2024 pechler-Speicher et al. 2025)
Our contribution. We introduce a new procedure for approximating general directed graphs G with adjacency matrices E {0, 1j xN by low-rank matrices C that have a special interpretation: the approximating graph consists of set of overlapping bipartite components. Namely, there is set of K < N pairs of node communities (44, V.). I..... K, and each pair defines a weighted bipartite component, in which edges connect each node of 14; to each node of V; with some weight r: (that can be negative). The full graph C is defined as the sum of all of these components, called blocks or directed communities, where the different communities can overlap (see Figure I for visualization of the approximating graph). We demonstrate how processing C' instead of A leads to models that solve downstream task in linear time and space complexity with respect the number of nodes, as opposed to standard MPNNs that are linear in the number of edges.
To fit to A, we consider a loss function (C)) defined as a weighted norm of A C, namely, a standard norm weighted element-wise by a weight matrix Q E (0, NxN The goal of using weights to balance the contributions of edges and non-edges. The weight matrix Q is chosen adaptively, depending on the target adjacency matrix A. We consider a weighted cul norm, denoted by (C))), as the approximation metric. The cut norm a well-established graph similarity measure that quantifies the maximum discrepancy in their connectivity structure. It enables graph approximations with rank independent the number of nodes for dense graphs. However, for sparse graphs, the standard cut-metric is dominated by non-edges, which degrades approximation quality. This motivates the use of a weighted cut-norm that balances the contributions of edges and non-edges. The cut norm also has probabilistic interpretation that we discuss in Section 3 and Appendices B Computing the cut norm is NP-hard, which prohibits explicitly optimizing it. To solve this issue, we prove that is possible to minimize weighted Frobenius norm || ClIF instead of the cut norm, and guarantee that the Frobenius minimizer C' has small cut error om ('") even if the minimum || A C* Up itself large. For that, we formulate a version of the Weak Regularity Lemma (WRL) (Frieze & Kannan 1999) that we call the semi-constructivg densifying directional seft weak regularity lemma, or in short the Densifying Weak Regularity Lemma.
and C
The WRL asserts that one can approximate any graph with E edges and N nodes up error w.r.t. the cut metric by low-rank graph consisting of N/(vFec) intersecting communities. For more details on the standard WRL see Section B Our approach, which is an extension of the ICG method (Finkelshtein et al. 2024a), is different from other forms of the WRL in number of ways:
While some variants of the WRL only prove existence Láazzó Miklós Lovász 2007 we find the approximating low-rank graph as the solution to an "easy to optimize" loss function (hence our approach is constructive).
2

---

Published as a conference paper at ICLR 2026
While some versions of the WRL (Frieze & Kannan 1999) propose algorithm that provably obtains the approximating low-rank matrix, these algorithms are exponentially slow and not applicable in practice (for example, see Section 7 of Finkelshttei al. (2024a)). Instead, the loss function we introduce can be efficiently optimized via gradient descent. While the optimization procedure is not guaranteed to find the global minimum since the loss is non-convex, it nevertheless produces high-quality approximations in practice (hence the term constronstructive). To facilitate gradient descent-based optimization, we relax the combinatorial problem (hence the term soft).
Previous versions of the WRL consider undirected graphs, while we treat general directed graphs (hence the term directional).
While previous versions of the WRL required N/ N/(vEe² communities for e error w.r.t. the standard cut metric, we guarantee an error in weighted cut metric with only 1/e² communities. Hence, the number of communities in our method is independent of any property of the graph, including the number of nodes and sparsity level. This capability directly follows from balancing the importance of edges and non-edges in our optimization target. As result. it leads to a formal approach for approximating sparse large graphs by dense low rank graphs, justifying the term densifying. We emphasize that this independence of the number of communities on the sparsity level is not merely an artifact of carefully renormalizing the loss to artificially facilitate the desired error bound. Rather, the loss function is deliberately designed to promote denseness when approximating graphs. The ability to efficiently densify a given graph can improve downstream tasks like node classification, as, in some sense, the densified version C* of the graph A strengthens the connectivity patterns of the graph. We stress that as opposed to naive densification approaches, our method improves both computational complexity and accuracy.
In this paper, we introduce a new graph similarity measure that enables efficient approximation of any graph, including sparse and directed ones. We develop non- con-trivial extension of the ICG method called the Intersecting Blocks Graph (IBG). Our central theoretical result shows that any graph, sparse dense, can be approximated with error that depends only on the desired accuracy, independent of graph size or sparsity level. This advancement enables the design of IBG Neural Networks (IBG-NNs), which operate directly on the IBG representation of any graph. IBG-NNs allow solving downstream tasks such as node classification, Seatioltemporal graph analysis, and knowledge graph completion in (NN) operations rather than (E). We demonstrate that our approach achieves state-of-the art accuracy standard benchmarks, while being very efficient. For background on the predecessor of our method, ICG (Finkelshtein et al. 2024a), see Appendix For a comparison of our method with ICG, see SectionsJaars and M.2.
2 BASIC DEFINITIONS AND NOTATIONS
We denote matrices by boldface uppercase letters, e.g.. D, vectors by boldface lowercase d, and their scalar entries by the same lowercase letter de with subscript for the index.
Graph signals. We consider directed (unweighted) graphs G with sets of N nodes V [N]] (1,...,N,, E edges & C V x V, adjacency matrix A = ( E (0,1) NxN, and node feature matrix X (II N.D E [-1, called the signal. We follow the graph signal processing convention and represent the data as graph-signals G X). We emphasize that signals are always normalized to have values in 11, 1]. which does not limit generality as the units of measurement can always be linearly changed. All constructions also apply to signals with values in IR, but for simplicity of the analysis we limit the values to [].
We denote the j-th column of the matrix Q by Q..g. and the i-th row by Qi.-. We often also denote the i-th row by q, and respectively denote Q ( We identify vectors v (vz ) with corresponding functions i + Us- Similarly, X (nn = hn We demote by diag(r) E IR x the diagonal matrix with diagonal elements r E R
treat X function X [N] - R with
Frobenius norm. The weighted Frobenius norm of square matrix D R NXN with respect to 1/2 Denote
the weight Q E (0, NxN is defined to be | == (EV 9.
En dl (.))))
|DI|p = || D Ir: where 1 is the all-1 matrix. The Frobenius norm of a signal Y E RRN is defined
3

---

Published as a conference paper at ICLR 2026
by | P V ND Σn Ep=E vh.j- The weighted Frobenius norm with weights a, > 0f
matrix-signal (D, Y) is defined by II(D,)) |(D, [ID, V D P + B
3 WEIGHTED GRAPH SIMILARITY MEASURES
Weighted cut-metric. The cut-metric is a graph similarity measure based on the cut-norm. Below, define it for graphs of the same size; extensions to arbitrary graphs graphons (see (Lászlō
Miklós Lovász 2007) for graphons, and (Levie 2023) for graphon-signals).
Definition 3.1. The weighted matrix cut-norm of D E RNNN with weights Q E (0, 00) NxN
defined to be
|Plloo
1
ΣΣ iEM
max Ens Ris U.V.[N]
The signal cut-norm Y E NND is defined to be
Y DN
1
max UCIN
Σ 3o.
SEU
The weighted matrix-signal cut-norm of (D, Y), with weights ar, B, >> 0, is defined be
[[D,, " [[ Y) Yllao == a a + B
Note that Finkelshtein et al. (2024a) used the weighted cut-norm | == = (N²/E) DIl
Densifying cut similarity. A key limitation of the cut-metric in sparse graphs arises from the dominance of non-edges in the graph structure. Sparse graphs, such as those common in link prediction and knowledge graph completion (Dettmers et al., 2018), often have small number of edges relative to non-edges. This imbalance causes the cut-metric to be dominated by non-edges unless they properly weighted. We believe that this imbalance significantly impacted the quality of the approximating ICG in FFinellshtein et al. (2024a), which uses the unweighted cut-metric, i.e. with Q 1, and consequently the underperformance of downstream tasks which operate the ICG.
Motivated by this limitation, we define a similarity measure that better addresses the structural imbalance inherent in sparse graphs. We propose the densifying similarity, modification of the cut-metric that lowers the contributions of non-edges w.r.t. the standard cut-metric. We define weighted adjacency matrix Q that assigns a weight to non-edges and 1 to edges. The parameter is chosen based on the desired balance, controlled by factor 1,, which determines the proportion of non-edges relative edges. For a detailed derivation of the definition from motivating guidelines, and its relation to negative sampling in knowledge graph completion and link prediction, see Section C
Definition 3.2. Let A E (0, NxN be an unweighted adjacency matrix, and I 0. The densifying cut similarity between the target A and any adjacency matrix B N is defined to be
()(AI(B) on. ( (1 + r) A Blloo
where the weight matrix QA
TE/N2
QA = QA. :0 (1- with Eg, 1- (B/N2))
(2)
Given a, 3 such that a a B 1, the densifying cut similarity between the target graph-signal (A, X) and the graph-signal (A','') X') is defined to be
(AA (A', = 00 a.r. ((A, ((A, (XAAI X')) = (A)
+ B
X'I
We stress that the weighted Frobenius norm with the weight from Definition 3.2 is well normalized, iee. (1 + T) || = 1, suggesting that the norm on ((A, (A, X]] (A', X meaningfully standardized. Namely, we expect on (A, (A',, (())'))) have magnitude of the order of 1 when B is a "bad" approximation of A, and to be & when is a "good" approximation. Also not that the standard cut metric is retrieved when r N2 //
4

---

Published as a conference paper at ICLR 2026
4 APPROXIMATIONS BY INTERSECTING BLOCKS
4.1 INTERSECTING BLOCK GRAPHS
For any subset of nodes U [N], the indicator function 1 is defined 11((t) if i E U and 0 otherwise. As explained above, we treat Nu as vector in RN Denote by X the set of all such indicator functions. We define an Intersecting Block Graph (IBG) with K classes (K-IBG) low-rank graph-signal (C, P) with adjacency matrix and signals given respectively by
K
C
ErjDu By
P
Σ Ju + by, 5=1
where E R. fj. by E RD, and U₁ V3 C [N]. Next, we relax the {0, 1--valued hard indicator functions Tu By to soft affiliation functions with values in R2 defined next, allow continuously optimizing IBGs. Definition 4.1 is taken from Finkelshtein et al. 2024a).
Definition 4.1. A set Q of vectors [N] R that contains is called soft affiliation model.
Definition 4.2. Let N, and let Q soft affiliation model. We define [Ω] C RNNN R to be the set of all elements of the form (ruv" ,uf" + bb"), with u, v E Q. r E R and f.b E RD. We call [2] the soft rank-1 intersecting block graph (IBG) model corresponding to Q. Given E N. the subset [2] of RNNN x of all linear combinations of K elements of [Q] is called the soft rank- K IBG model corresponding to Q.
In matrix form, IBG (C, P) NNN NXD in [Q] can be written
C U diag(r) and P P-UF+VE VB
via the target community affiliation matrix U E RNN the source community affiliation matrix V E R-NK the community magnitude vector r E RK the target community feature matrix
F E RKxD and the source community feature matrix B E RRKDD.
4.2 THE DENSIFYING REGULARITY LEMMA
Directly minimizing the densifying cut similarity (or cut metric) is both numerically unstable and computationally difficult since involves maximization step, making the optimization a min-max problem. To overcome this, we introduce middle-grount solution, providing an efficient semi- constructive version of the weak regularity lemma for intersecting blocks. The approach termed semi-constructive because it formulates the approximating graph the solution to an "casy-to-solve" optimization problem that can efficiently handled using standard gradient descent techniques.
The theorem generalizes the semi-constructive WRL based intersecting communities of Finkelshtein et al.] (2024a) in three main ways: (1) extending the theorem to directed graphs and the densifying graph similarity, instead of undirected graphs and the cut norm, (2) introducing certificate for testing that the high probability event in which the cut similarity error small occurred, and the key novelty of this theorem (3) it addresses major limitation of the previous work by providing a bound that is independent of the graph size for both sparse and dense graphs, whereas the bound in Finkelshtein et al. (2024a) depended on the graph size for sparse graphs. For a more extensive comparison between our approach and Finkelshtein et al. (2024a) see Appendix
Theorem 4.1. Let (A, X) be siaph- K E E 8 > O, and let Q be a soft affiliation model. Let a, B > 0 such that a + B 1. Let > 0 and let QA be the weight matrix defined in Definition 3.2
Let R 2 1 such that K/ E N. For every k N, lei
(1 + 8)
min (C.P)
|[A, X) - (C, ()IP) P) [(AX))-CCC,
Then,
1. For every m E any IBG (C',P) E [2)m that gives a close-to-best weighted Frobenius approximation of (A, X) in the sense that
(A X) (C", P' P')lEeAA S Ams
5

---

Published as a conference paper at ICLR 2026
also satisfies
8...8 (IA,") P')) (Va(L+1)) + vBN mm
Mm++1
(5)
1+
2. If m uniformly randomly sampled from [K], then in probability 1
7m++1
S V g R(1+6)
V pm I+8
(6)
K
Specifically, in probability
R. any (C*, P*) 12m which satisfies (4)
also satisfies
R(1 + 6)
L (,,, (A, (C", P')) S V2+ 8
K
The proof of Theorem 4.1 is Appendix D
Specifically, the three main ways in which Theorem 4.1 generalizes ICG IBG are depicted in: (1) The use of directional IBGs, (2) the deterministic certificate for the high probability event given by Item L and (3) the approximation bound in Item which is independent of graph sparsity.
4.3 OPTIMIZING IBGs WITH ORACLE FROBENIUS MINIMIZERS
Suppose there exists oracle optimization method that solves 4 in Tx operations for any S K. 1h. motivates mottivates the following algorithm for approximating a graph-signal by an IBG.
Randomly sample m E [ By Item 2 of Theorem 4.1 the approximation bound 7 is satisfied
in high probability (1 1/R).
To verify that 7 really happened for the given realization of m. estimate the left-hand-side of (6). using the oracle optimizer 27k operations (computing both Tm and 1m+1), checking if (6) is satisfied. If it is, guarantees (7) by (5).
. If the bound 6 is not satisfied (in probability less than 1) resample m and repeat.
The expected number of resamplings of is RR/R- 1). so the algorithm's expected runtime to find an IBG satisfying 7 is 27x RR 1). In practice, instead of an oracle optimizer, we apply gradient descent to estimate the optimum of the left-hand side of (4) which requires Tx = O(E)
operations by Theorem 4.2) This makes the algorithm as efficient message passing in practice.
4.4 FITTING INTERSECTING BLOCKS USING GRADIENT DESCENT
In this section, we propose an efficient computation for fitting IBGs to directed graphs based on Theorem 4.1 (minimizing the left-hand-side of {4) via gradient descent). As the soft affiliation model, we consider all vectors in [0. 1] In the notations of 3.. we optimize the parameters U. V E [o, 1 R.K and F, B R minimize the weighted Frobenius norm
F,
A U V I + 3 | -F - VB -
(8)
In practice, we implement U.V E N matrices U', V' E ER NxK setting U Sigmoid(U') and V Sigmoid(V').
NK by applying sigmoid activation function to learned
Optimizing (8) naïvely requires O(N operations, as the matrix A U diag(r)V E NRN is not sparse nor low-rank. However, we can exploit the sparsity of A and the low-rank structure of U didag( (r) VT separately to enable an efficient computation with time and space complexities of O(K2N KE) and O(KN E), respectively.
Proposition 4.2. Let A = (at.) be an adjacency matrix of an unweighted graph with E edges. The graph part of the sparse Frobenius loss (8) can be written as
|| U diag(r) T 11Al
EE,
Tr ((V V) diag(r)(U U) diag(r))
(1+I)E
(1+ Σ Σ U. diag(r) (VT) (V ais (1+T)E Σ
EET
Σ JEN(())
Σ (U,,, diag(r) (VT).,))
I=1 JEN())
where QA and eg. are defined in ( Computing the right- hight-hand-side and its gradients with respect to U, V and has time complexity OK2 N K F),, and space complexity of O(KN N + F)).

---

Published as a conference paper at ICLR 2026
We prove Proposition 4.2 in Section E The parametres of the IBG, U, V, r. F, and B, are optimized
efficiently using gradient descent on Equation ( but restructured like Proposition 4.2
4.5 THE LEARNING PIPELINE WITH IBGS
When learning on large graphs using IBGs, the first step is fitting an IBG to the given graph. This done once with little to no hyperparameter tuning in (EE) time and memory complexity. The second step is solving the task, e.g., node classification. This step typically involves an extensive hyperparameter search. In our pipeline, the neural network processes the IBG representation of the data, instead of the standard graph representation. This improves time complexity from (EE) to (NN). Thus, when searching through S E N hyperparameter configurations, the whole search takes OSSN) time, while learning directly the graph would take OSE)). The efficiency of our pipeline is even more pronounced in apatio-temporat prediction, where the graph remains fixed while node features evolve over time. Here, the IBG is fitted to the graph only once, regardless of the time steps.
Initialization of IBG. In Appendix we explain how to use a low-rank SVD of the graph to efficiently initialize rank K IBG, before the gradient descent minimization of Equation (8) When the graph is too large to fit in memory, we also propose an efficient randomized SVD algorithm for approximating the SVD while only loading fraction of the graph into memory (Appendix G.2).
SGD for fitting IBGs to large graphs. Fitting an IBG to a graph requires ((F) memory complexity, which may exceed the GPU capacity in some situations. To solve this, in Appendix HH we propose sampling approach for optimizing the IBG, which reduces the memory complexity, allowing fitting IBGs large graphs hardware with limited memory.
PROCESSING IBGS WITH NEURAL NETWORKS
Graph signal processing with IBG. Finkelshtein et al. (2024a) proposed signal processing paradigm for learning on ICGs. In this section we provide an extended paradigm for learning on IBGs, which runs in O(N K) operations per layer, which is often faster than the OEE) complexity of MPNNs. Let U. V N be target and source community affiliation matrices. We call R Nx
the node space and R the community space. We use the following operations process signals:
Target synthesis and source synthesis are the respective mappings J UF, B VB from the community space to the node space, in ONN
Target analysis and source analysis are the respective mappings X U or ViX from the node space to the community space, in ONN
Community processing refers to any operation that manipulates the community feature vectors F and B (e.g., an MLP) in O(K² D²) operations (or less).
. Node processing is any function that operates on node features in O(ND²) operations.
IBG Neural Networks. We propose an IBG-based architecture (IBG-NN) defined as follows. Let D(0) denote the dimension of the node features at layer and set the initial node representations as ( X. Then, for layers 0 & l & L 1, the node features are defined by
H H (f+1)
= (0f (H!)) + Og +0g
(VB()))
H =o (0: (11!") +0 (UF())).
and require O(D(NK + KD + ND)) operations. The final representation, used for node-level predictions, is taken as (L) = H + H(")) where I and O₂ are MIPss or multiple layers of deepsets. ( ((t) kx are taken as trainable parameters, and o is non-linearity. See Sections to L for further details and comparisons with MPNNs and ICG-NNs.
IBG-NNs for spatio-temport
graphs. Given a graph with fixed connectivity and time-varying node features, we fit the IBG to the graph once. We then train model on the frozen IBG predict the next-step signal from past time steps. Thus, given training signals, an IBG-NN requires O(TN K D² operations per epoch, compared O(TED²) for MPNNs, with the preprocessing time remaining independent of T. Thus, as the number of training signals increases, the efficiency gap between IBG-NNs and MPNNs becomes more pronounced.
7

---

Published as a conference paper at ICLR 2026
6 EXPERIMENTS
In this section, we conduct experiments addressing the core research questions:
Q1 Does IBG-NN 's computational efficiency match theoretical expectations practice when compared traditional MPNNs dense and sparse graphs?
Q2 Do IBG-NN's theoretical guarantees for approximating arbitrary directed and sparse graphs translate to improved empirical performance compared to traditional GNNs and ICG-NN?
Q3 How does IBG-NN perform against other graph condensation methods, across varying conden- sation ratios on large-scale graph benchmarks?
In Section M we further expand our evaluation with a series of additional experiments and ab- lations. We conduct an ablation study across additional domains, showcasing the versatility and applicability of IBG-NN on Spatio-femporal tasks (Section M.I.I,, Knowledge graph comple- tion (Section M.I.2). and node classification using subgraph SGD (Section M.1.3), achieving state-of-the-art performance. We further validate the importance of densification (Section M.3) with additional comparisons to ICG-NN. We analyze the computational advantages of IBG-NN with memory complexity experiments (Section M.4.I). and provide ablation the number of communities (Section M.2), showcasing how adding communities can lead to performance improve- ments and better approximations. Lastly, test our SVD initialization method (Section M.4.2). demonstrating improvements in convergence time of IBG approximation.
Full hyperparameter details are provided in Section P and codebase is publicly available at: betps://anonymoult 4open. scwenceer//iinnee.oo IBGNN
6.1 THE EFFICIENT RUN-TIME OF IBG-NNS
Setup. To evaluate the efficiency of IBG-NN (Q1), measure the forward pass runtimes of
IBG-NN and DirGNN (Rossi et al. 2024 a simple and efficient method for directed graphs. We then compare it on dense Erdōs-Rényl ER(n. p 0.5) graphs and sparse ER(n, p 25/n) n) graphs with up to 7, 000 nodes, We sample 128 node features per node, independently from U|0, 1]. Both models use hidden and output dimension of 128, and 3 layers.
Results. Figure 2 shows that the runtime of IBG-NN is consistently faster than DirGNN across both dense and sparse graph settings. For dense graphs. IBG-NN runtime exhibits strong square root relationship when compared to DirGNN. This matches our theoretical expectations given that IBG-NN and MPNNs have O(N) and OEE) complexity respectively. For sparse graphs, the scaling relationship appears linear. This still aligns with our theoretical expectations, as in this setting the number of edges scales linearly with N. Still, compared DirGNN, IBG-NN achieves significant speedups of 5.68x and 5.26x for K = 10 and K 100 respectively. Notably, even when using K 100 communities, which exceeds the average degree of 25 used in the experiments, IBG-NN still maintains faster performance. This advantage stems from IBG-NN's simple and efficient operations compared to the complex message- sesssage-passing computations required by DirGNN.
ERin. pin) 29)
ERln, 0.5)
20
IBC-NW forward duration [mwee]]
35
NGN-NN forward duration
24
7.0602
22
25
K- 100
y 0,1981x + 18.1821
18
R² = 0.9411
15
y
16
K- 100
1.571// 3.1219
R7 m 0.9562
200
300
DIrGNN duration 1x10
DirGNN
[msec]
Figure 2: Runtime of K-IBG-NN as a function DirGNN forward pass duration on sparse
ER p 25/n) graphs (left) and dense E. 0.5) graphs (right) for K=10, 100.
8

---

Published as a conference paper at ICLR 2026
Table 1: Results on directed node classification benchmarks; top models colored First, Second, Third.
Model
Squirre
Chameleon
Tolokers
MLP
28,77 = 1.56
46.21 2.99
72.95# 1.06
GCN
Kipf & Welling
2017)
53,43 = 2.01
64.82 2.24 66.82 2.56
83.64 0.67
GAT
Velickovic al.
2018)
40.72 1.55
83.70+ 0.47
H&GCN Zhu et al. 2020)
61,90 1.40
46.21
2.99
73.35+ 1.01
GPR-GNN (Chien al.
22200)
74.801: 0.50
78.301 0.60
72.941 0.97
FSGNN Maurya a el al. 2021)
74.10 + 1.89
78.27 + 1.28
GloGNN Li el al. 2022b)
57.88 +: 1.76
71.21 + 1.84
73.39 1.17
DirGNN Rossi of al 2024)
75.13 = 1.95
79.74 = 1.40
FaberNet (Koke Cremers
2024
76.71 = 1.92
80.33 1.19
ICG-NN
Finkelshtein et al.
2024a
64.02 + 1.67
63.9 : 2.13
83.731 0.78
IBG-NN (undirected)
70.02 1.34
75.15 1.33
83.76 + 0.51
IBG-NN
77.63 1.79
15 1.13
83.76 + 0.75
6.2 THE IMPACT OF DIRECTIONALITY AND DENSIFICATION
Setup. To evaluate the impact of our theoretical guarantees (Q2), enabled by directionality and densification, we compare IBG-NN to ICG-NN (Finkelshtein et al. 2024a). and IBG-NN with an undirected optimization setting. This allows to isolate the contribution of each addition. We
evaluate IBG-NN on several directed benchmark datasets: Tolokers (Platonov et al. 2023). Squirrel, and Chameleon (Pei et al. (020)), following the 10 splits of Platonno et al. (2023): ; Pei al. (2020). We report average ROC AUC and standard deviation for Tolokers, and average accuracy and standard deviation for Squirrel and Chameleon. For Tolokers, we report the baselines MLP, GCN (Kipf & Welling 2017), GAT (Veličković et al., 2018), H,GCN (Zhu et al., 2020), GPR-GNN (Chien al., 2020). FSGNN (Maurya et al.) 2021). GloGNN (Li et al. 20226) and ICG-NN taken from Finkelshtein et al. (2024a). For Squirrel and Chameleon, we report the same baselines, as well as
FSGNN (Maurya et al.] 2021). DirGNN (Rossi et al., 2024) and FaberNet (Koke & Cremers) 2024
taken from (Koke & Cremers, 2024).
Results. Table establishes IBG-NNs as state state-of-the-ar for directed graphs, surpassing GNNs
specifically tailored for directed graphs, despite their quadratic scaling compared to IBG-NNs. The re- sults reveal that both directionality and densification contribute significantly to the strong performance of IBG-NN. Specifically, IBG-NN without directionality surpasses ICG-NN by 6% on Squirrel and 11.2% on Chameleon, improvements attributed to densification. Adding directionality provides additional improvements of 7.6% and 5% respectively, achieving datasets. For Tolokers, both IBG-NN variants achieve nearly identical performance with minimal improvement over ICG-NN. We believe this could be the result of Tolokers already being very dense, minimizing the benefits provided by densification. Similarly, the graph's 's directed structure may not contain meaningful directional patterns that improve node classification performance.
performance on both
6.3 IBG-NN ON LARGE-SCALE GRAPH BENCHMARKS
Setup. To evaluate IBG-NN's performance large graphs (Q3), compare IBG-NNs and their predecessor ICG-NN on the large graphs Reddit (Hamilton et al. 201 7a), Flickr (Zeng et al. 2019) Arxiv and Products datasets (Hu et al. (2020), following the data split provided in (Zheng et al. 2024). Accuracy and standard deviation are reported for experiments conducted with 5 different seeds over varying condensation ratios M1 where N is the total number of nodes, and M the number of sampled entries of the graph adjacency matrix. The graph coarsening baselines Random (Huang et al. 202I), Herding (Welling) 2009), K-Center (Sener & Savarese (017) and the graph condensation baselines GCOND (Jin et al. 20 SFGC (Zheng et al. 2024). GC-SNTK (Wang et al. 2024) and SimGC (Xiao et al. 2024) are taken from (Zheng et al. 2024] Wang et al.) 2024 Xiao et al. 2024). We note that a condensation ratio of 100% corresponds to a standard GCN for the baseline methods.
Results. Table Sable2demone demonstrates that subgraph SGD IBG-NN achieves sfateoo--hh-art performance, surpassing other coarsening and condensation methods that operate the full graph in memory,
9

---

Published as a conference paper at ICLR 2026
Table 2: Results on graph densification benchmarks; top models colored First, Second, Third.
Flickr
Reddit
Arxiv
Products 0.02%
Condensation
Random
44.0 0.4
0.2
41.2 1:2-4:01
2.2
93.9
47.1 3.9
Herding
43.9 43.9
44.4 1: 0.6
41.2
62.7 +: 1.0
71.0 + 1.6
93.9 0.0
52.4 = 1.8
55.1 + 0.3
K-Conter
43.2 4322 0.1
04
4
58.5 2.1
93.9
47.2 = 3.0
48.5
GOOND
4.11
4..1
4..2:1..11
89.6 +: 0.7
90.1 + 0.5
93.9 = 0.0
61.3 = 0.5
55.0 1: 0.8
SPGC
1.1
47.1
4..2.10.1
90.0 0.3
89.9 1. 0.4
93.9
65.5 1 0.7
61.7
GC-SNTK
468 0.1
46.5 0.2
4.12.10.11
64.4 - 0.2
SimGC
0.4
43.8
47.2
92.0 0.3
93.9
63.6 = 0.8
63.3
ICG-NN
52.7 02740011
90.7 92.6 1. 0.6
IRG-NN
50.511 0.1
$1.3 0.2
53.0
1
92.3 1 1.1
94.1 1. 0.5
64.4 1: 1.1
61.9 1 0.3
while also improving upon the performance its predecessor, ICG-NN. A comparison between graph coarsening methods and IBG-NNs can be found in Section A
7
CONCLUSION
We proved number communities for a given approximation error is independent any property of the graph, including size and sparsity. This contrasts previous formulations of the lemma, where the number of communities increased with graph size for sparse graphs. Our formulation is achieved by introducing the densifying cut similarity, which, when optimized, leads the approximating IBG to effectively den- sify the target graph. This enables fitting IBGs of very low rank (K O(1)) to large sparse graphs, while previous works required the target graph be dense for low rank approximations, We intro- duced IBG-NNs a network which operates on the IBG instead of the graph, and has O(N) time and memory complexity. IBG-NNs demonstrate state-of-the-as performance in multiple domains: node classification on directed graphs, spatio-temporal graph analysis, and knowledge graph completion.
comi-constructive version of the weak regularity lemma, in which the required
ACKNOWLEDGMENTS
This research was supported by grant from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel, and the United States National Science Foundation (NSF), (NSF-BSE, grant No. 2024660). and by the Israel Science Foundation (ISF grant No. 1937/23).
REPRODUCIBILITY STATEMENT
We provide public codebase with a complete implementation of all methods presented. All datasets used the experiments are publicly available benchmarks. We report full experimental settings, computational resources, and hyperparameters for all conducted experiments. Theoretical results are fully supported with rigorous proofs provided in the appendices.
ETHICS STATEMENT
This paper presents work whose goal is to advance the field of Machine Learning, and involves no human subjects or sensitive information. Our work is mostly theoretical, and poses no potentially harmful societal consequences.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Lei Bai, Lina Yao, Can Li, Xianzhi Wang, and Can Wang. Adaptive graph convolutional recurrent network for traffic forecasting. NeurIPS, 2020.
Maya Bechler-Speicher, Ben Finkelshtein, Fabrizio Frasca, Luis Müller, Jan Tönshoff, Antoine Siraudin, Viktor Zaverkin, Michael M Bronstein, Mathias Niepert, Bryan Perozzi, et Position: Graph learning will lose relevance due to poor benchmarks. In ICML, 2025.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In ICML, 2020.
Antoine Bordes, Nicolas Usunier, Alberto Farcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NewrIPS, 2013.
Christian Borgs, Jennifer Chayes, László Lovász, Vera T Sós, and Katalin Vesztergombi. Conver- gent sequences of dense graphs i: Subgraph frequencies, metric properties and testing. Advances in Mathematics, 2008
Wang Changping, Wang Chaokun, Wang Zheng, Ye Xiaojun, and S. Yu Philip. Edge2vec. ACM Transactions on Knowledge Discovery from Data (TKDD), 2020.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In ICLR, 2018.
Kewei Cheng, Jiahao Liu, Wei Wang, and Yizhou Sun. Rlogic: Recursive logical rule learning from knowledge graphs. In KDD, 2022.
Kewei Cheng, Nesreen K Ahmed, and Yizhou Sun. Neural compositional rule learning for knowledge graph reasoning. ICLR, 2023.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. ICLR, 2020.
Andrea Cini, Ivan Marisca, Daniele Zambon, and Cesare Alippi. Taming local effects in graph-based spatiotemporal forecasting. In NeurIPS, 2024.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. AAAI, 2018.
Petros Drineas, Ravi Kannan, and Michael W Mahoney. Fast monte carlo algorithms for matrices i: Approximating matrix multiplication. SIAM Journal on Computing, 2006.
Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molecular graphs. arXiv, 2020.
Ben Finkelshtein, ismail ilkan Ceylan, Michael Bronstein, and Ron Levie. Learning on large graphs using intersecting communities. In NeurIPS, 2024a.
Ben Finkelshtein, Xingyue Huang, Michael Bronstein, and ismail ilkan Ceylan. Cooperative graph neural networks. ICML, 2024b.
Alan Frieze and Ravi Kannan. Quick approximation to matrices and applications. Combinatorica, 1999.
Simon Geisler, Yujia Li, Daniel J Mankowitz, Ali Taylan Cemgil, Stephan Günnemann, and Cosmin Paduraru. Transformers meet directed graphs. In /CMI., 2023.
William L.. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NewrlPS, 2017a
William Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 2017b.

---

Published as a conference paper at ICLR 2026
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. In NeurIPS, 2020.
Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. In KDD, 2021.
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. In ICLR, 2021.
Wei Jin, Xianfeng Tang, Haoming Jiang, Zheng Li, Danqing Zhang. Jiliang Tang, and Bing Yin. Condensing graphs via one-step gradient matching. In KDD, 2022.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Thomas N Kipf and Max Welling, Variational graph auto-encoders. arXiv, 2016.
Stanley Kok and Pedro Domingos. Statistical predicate invention. In ICML, 2007.
Christian Koke and Daniel Cremers. Holonets: Spectral convolutions do extend to directed graphs. In ICLR, 2024.
Balázs Szegedy László Miklós Lovász. Szemerédi's lemma for the analyst. GAFA Geometric And Functional Analysis, 2007.
Ron Levie. A graphon-signn signal analysis of graph neural networks. In NeurlPS, 2023.
Rui Li, Jianan Zhao, Chaozhuo Li, Di He, Yiqi Wang, Yuming Liu, Hao Sun, Senzhang Wang, Weiwei Deng, Yanming Shen, al. House: Knowledge graph embedding with householder parameterization. In ICML, 2022a.
Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily, ICML, 2022b.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. In ICLR, 2018.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In NeurlPS, 2021.
László Miklós Lovász. Large networks and graph limits. In volume 60 of Colloquium Publications, 2012.
Zaheer Manzil, Kottur Satwik, Ravanbakhsh Siamak, Póezos Barnabás, Salakhutdinov Ruslan, and Smola Alex. Deep sets. In NeurIPS, 2017.
Sohir Maskey, Ron Levie, and Gitta Kutyniok. Transferability of graph neural networks: An extended graphon approach. Applied and Computational Harmonic Analysis, 2023.
Sohir Maskey, Raffaele Paolino, Aras Bacho, and Gitta Kutyniok. A fractional graph laplacian approach to oversmoothing. In NeurlPS, 2024.
Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Improving graph neural networks with simple architecture design. arXiv, 2021.
Joel Oskarsson, Tomas Landelius, Mare Peter Deisenroth, and Fredrik Lindsten. Probabilistic weather forecasting with hierarchical graph neural networks. NeurlPS, 2024.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2020.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? In ICL.R, 2023.
12

---

Published as a conference paper at ICLR 2026
Meng Qu, Junkun Chen, Louis-Pascis Xhonneux, Yoshua Bengio, and Jian Tang. Rnnlogic: Learning logic rules for reasoning on knowledge graphs. In ICLR, 2020.
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. convolutional networks on node classification. In ICLR, 2020.
Dropedge: Towards deep graph
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. In ICML 2020 Workshop on Graph Representation Learning and Beyond, 2020.
Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca, Stephan Günnemann, and Michael M Bronstein. Edge directionality improves learning on heterophilic graphs. In LoG, 2024.
Yousef Saad. Numerical methods for large eigenvalue problems: revised edition. SIAM, 2011.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In ICLR, 2017.
Igor G. Smit, Jianan Zhou, Robbert Reijnen, Yaoxin Wu, Jian Chen, Cong Zhang, Zaharah Bukhsh, Yingqian Zhang, and Wim Nuijten. Graph neural networks for job shop scheduling problems: A survey. Computers & Operations Research, 2025.
Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR, 2019.
Lloyd N. Trefethen and David Bau. Numerical Linear Algebra, Twenty-fifth Anniversary Edition. Society for Industrial and Applied Mathematics, 2022.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In ICML, 2016.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Lin Wang, Wenqi Fan, Jiatong Li, Yao Ma, and Qing Li. Fast graph condensation with structure-based neural tangent kernel. In WWW, 2024.
Max Welling. Herding dynamical weights to learn. In JCML, 2009.
Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chenggi Zhang. Graph wavenet for deep spatial-temporal graph modeling. In IJCAI, 2019.
Zhenbang Xiao, Yu Wang. Shunyu Liu, Huiqiong Wang, Mingli Song, and Tongya Zheng. Simple graph condensation. In ECML-PKDD, 2024.
Zuoyu Yan, Tengfei Ma, Liangeai Gao, Zhi Tang, and Chao Chen. Link prediction with persistent homology: An interactive view. In ICML, 2021.
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In ICLR, 2014.
Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In NeurIPS, 2017.
Jaewon Yang and Jure Leskovec. Overlapping community detection at scale: a nonnegative matrix factorization approach. In Association for Computing Machinery, 2013.
Zhitao Ying, Jiaxuan You. Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In NeurIPS, 2018.
Fang Yujie, Li Xin, Ye Rui, Tan Xiaoyan, Zhao Peiyao, and Wang Mingzhong. Relation-aweer aware graph convolutional networks for reltionclationll network alignment. ACM Transactions on Intelligent Systems and Technology, 2023.
13

---

Published as a conference paper at ICLR 2026
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In ICLR, 2019.
Xin Zheng, Miao Zhang, Chunyang Chen, Quoc Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan. Structure-free graph condensation: From large-scale graphs to condensed graph-free data. In NeurIPS, 2024.
Houquan Zhou, Shenghua Liu, Danai Koutra, Huawei Shen, and Xueqi Cheng. A provable framework of learning graph embeddings via summarization. In AAAI, 2023.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In NeurlPS, 2020.
Zhaocheng Zhu, Zuobai Zhang, Louis-Paseal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. In NeurIPS, 2021.
Daniel Zilberg and Ron Levie. Pieclam: A universal graph autoencoder based on overlapping inclusive and exclusive communities. In ICML, 2025.
14

---

Published as a conference paper at ICLR 2026
A RELATED WORK
Intersecting Community Graphs (ICG). Our work continues the ICG setting of Finkelshtein et al. (2024a), which introduces weak regularity lemmas for practical graph computations. The work of Finkelssstiiin et al. (2024a) presented a pipeline for operating on undirected, non-sparse graphs. Similarly to our work. Finkelshtein et al. (2024a) follow two stage procedure. In the first stage, the graph is approximated by learning a factorization into undirected communities, forming what they call an Intersecting Community Graph (ICG). In the second stage, the ICG is used to enrich a neural network operating on the node features and community graph without using the original edge connectivity. This setup allows for more efficient computation, both in terms runtime and memory, since the full edge structure of the graph, used in standard GNNs, can be replaced with much smaller community-level constructive weak regularity lemma presented in (Finkelshtein et al. 2024a) shows any graph can be approximated in cut-norm, regardless of its size, by minimizing the easy to compute Frobenius error.
hyaph-especillly useful for graphs with high average degree. The
More concretely, ICG with K communities is just like an IBG with only node features (no edge- features), but with the transmitting and receiving communities being equal = =V. Namely, an ICG can be represented by triplet of communiit affiliation matrix Q RN* community magnitude vector r E R&K and community feature matrix F E RKKD. An ICG (C, P) with adjacency matrix C' and signal P is then given by
C= dia and P QF
where diag(r) is the diagonal matrix in R with as its diagonal elements. Here, K is the number of communities, N the number of nodes, and the number of edges.
When approximating a graph-signal (A,X) the measure of accuracy, or error, in (Finkelshtein ctt al. 2024a) is defined to be the standard (unweighted) cut metric (A, X) (C, P) The semm-constructive regularity lemma of Finkelshtein al. (2024a) states that it is enough to minimize
the standard Forbenius error (A,, X)= (C, P)Ip in order to guarantee
(4, - (C, P)ll_ ONN/VKF)
Looking at (9) it is clear that in order to guarantee small approximation error in cut metric, the number of communities must increase as N/VE E becomes larger. Specifically, the number of communities is independent of the size of the graph only when E N i.e. the graph is dense. Hence, the ICG method falls short for sparse graphs
Our IBG method solves this shortcoming and more. For example, a main contribution of our method is densification mechanism, supported by our novel densifying cut similarity measure and our densifying regularity lemma, which is a non-trivial continuation and extension of the semi- constructive weak regularity lemma of Finkelshtein al. (2024a). Please see Appendix J for detailed comparison of our IBG method to ICG.
Cluster Affiliation models (BigClam and PieClam). A similar work is PieClam Ziilerrg & Levie 2025). extending the well known BigClam model (Yang & Leskoved 2013). which builds probabilistic model of graphs as intersections of overlapping communities. While BigClam only allows communities with positive coefficients, which limits the ability to approximate many graphs, like bipartite graphs, PieClam formulates graph probabilistic autoencoder that also includes negative communities. This allows approximately encoding any dense graph with a fixed budget of parameters per node. We note that as opposed ICG and PieClam, which can only theoretically approximate dense symmetric graphs with (11) communities, our IBG method can approximate both sparse and dense (non-s) (non-symmetre symmetric in general) graphs with (1) communities via the densification mechanism (the densifying constructive regularity lemma with respect to the densifying cut similarity).
GNNs for directed graphs. The standard practice in GNN design is to assume that the graph is undirected (Kipf & Welling, 2017). However, this assumption not only alters the input data by discarding valuable directional information, but also overlooks the empirical evidence demonstrating that leveraging edge directionality can significantly enhance performance (Rossi et al. 2024). For instance, DirGNN (Rossi et al. (024) extends message- passing neural networks (MPNNs) to directed graphs, while Geisler et al. (2023) adapts transformers for the same purpose. FaberNet (Koke & Cremers 2024) generalizes spectral convolutions to directed graphs, all of which have led to improved performance. Co-GNN (Finkelshtein et al. 2024b) demonstrates the advantage of learning edge
15

---

Published as a conference paper at ICLR 2026
directionality over using conventional undirected graph representations. Furthermore, the proper handling of directed edges has enabled et al. (2024) to extend the concept of oversmoothing to directed graphs, providing deeper theoretical insights. IBG-NNs also capitalize edge directionality. achieving notable performance improvements over their predecessor ICG-NNs (Finkelshtein et al. 2024a), as demonstrated in Section [M..T] When compared to existing GNNs designed for directed graphs, IBG-NNs offer a more efficient approach to signal processing. Specifically, for IBG-NNs to outperform message-passing- passsng--assedd GNNs in terms of efficiency, the condition KN- < E' must hold, Such a choice of K typically produces good performance for most graphs. This efficiency advantage allows IBG-NNs to make better use of the input edges while being more efficient than traditional GNNs.
Graph Pooling GNNs. Graph pooling GNNs generate a sequence of increasingly coarsened graphs by aggregating neighboring nodes into "super-nodes" (Ying et 20188) |Bianchi et al. (2000) where standard pesssag-passing is applied on the intermediate coarsened graphs. Similarly, in IBG- NNs, the signal is projected, but onto overlapping blocks rather than disjoint clusters, with several additional key distinctions: (1) The blocks in IBG-NNs are overlapping and cover large regions of the graph, allowing the method to preserve fine- ane-grained, projection, unlike traditional graph pooling approaches. (2) Operations on community features in IBG-NNs possess global receptive field, enabling the capture of broader structural patterns across the graph - an extremely difficult task for local graph pooling approach. (3) IBG-NNs diverge from the conventional snessage-passinggg framework: the flattened community feature vector, which lacks symmetry, is processed by a general multilayer perceptron (MLP), whereas message-passing neural networks (MPNNs) apply the same function uniformly to all edges. (4) IBG-NNs operate exclusively on an efficient data structure, offering both theoretical guarantees and empirical evidence of significantly improved computational efficiency compared to graph pooling methods.
signal details during
Graph reduction methods. Graph reduction aims to reduce the size of the graph while preserving key information. can be categorized into three main approaches: graph sparsification, graph coarsening and graph condensation. Graph sparsification methods (Hamilton et al. 2017a Zeng cct al. 2019: Chen et al. 2018 Rong et al., 2020 approximate a graph by retaining only a subset of its edges and nodes, often employing random sampling techniques. Graph coarsening (Fey et al. 2020, Huang et al. (02T)) clusters sets of nodes into super-nodes while aggregating anter-group edges into super-edges, aiming to preserve structural properties such as the degree distribution (Zhou et al., 2023). Graph condensation (Jin et al.) (02T) generates a smaller graph with newly created nodes and edges, designed to maintain the performance of GNNs on downstream tasks.
While subgraph SGD in IBG-NNs also involves subsampling, it differs fundamentally by providing provable approximation of the original graph. This contrasts with graph sparsification for example- where some, hopefully good heuristic-based sampling is often employed. More importantly, subgraph IBG-NNs offer a subgraph sampling approach for cases where the original graph too large fit in memory. This contrasts with the aforementioned coarsening and condensation methods, which lack a strategy for managing smaller data structures during the computation of the compressed graph.
Graph reduction methods generally rely on locality. applying message- -aagggngggiiggggggg on the reduced graph. In particular, condensation techniques require O FEM operations to construct smaller graph Din et al. (202T); ZZhen et al. (2024); Wang et al. (2024), where E is the number of edges in the original graph and M is the number of nodes in the condensed graph. In contrast, IBG-NNs estimate the IBG with only OEE) operations.
Furthermore, while conventional reduction methods process representations on either an iteratively coarsened graph or mappings between the full and reduced graphs, IBG-NNs incorporate fine-grained node information at every layer, leading to richer representations.
Cut metric in graph machine learning. The cut metric is useful similarity measure, which can separate any non-isomorphic graphons Lovász (012). This makes the cut metric particularity useful in deriving new theoretical insights for graph machine learning. For instance, {Levie 2023)
demonstrated that GNNs with normalized sum aggregation cannot separate graph-signals that are close to each other in cut metric. Using the cut distance as a theoretical tool, (Maskey et al. 2023) proves that spectral GNNs with continuous filters are transferable between graphs in sequences of that converge in homomorphism density. Finkelshtein et al. (2024a) introduced semi constructive weak regularity lemma and used it to build new algorithms on large undirected non-sparse graphs. In
16

---

Published as a conference paper at ICLR 2026
this work introduce new graph similarity measure the densifying cut similarity, which gives higher importance to edges than non-edges in a graph. This allows us to approximate any graph using a set of overlapping bipartite components, where the size of the set only depends on the error tolerance. Similarly to Fiinellshtein et al. (2024a), we present a semi constructive weak regularity lemma. As oppose to Finkelsshteiin et al. (2244)), using our novel similarity measure, our regularity lemma can be used to build new algorithms on large directed graphs which are sparse
B THE WEAK REGULARITY LEMMA
Consider graph G with a node set V [N] = [1, [I.....N) and an edge set & C V. We define an equipartition P = {Vi,.. ........ V as partition of V into k sets where | S 1 for every 1 S i,j S k. For any pair of subsets U, S C V denote by (c( the number of edges between U and S. Now, consider two node subsets U S V. If the edges between V. and V were to be uniformly and independently distributed, then the expected number of edges between 2/ and would
be
&
ea(V,, V3) MIIV
(P4.5) ΣΣ
M ns).
Using the above, we define the irregularity:
irrega(P) = max U
lea(U, - ep (u, ()) /
(10)
The irregularity measures how non-random like the edges between [V}} behave.
We now present the weak regularity lemma.
Theorem B.1 (Weak Regularity Lemma Frieze & Kannan 1999)). For every >> O and every graph G (V.E), there is an equipartition P = (Vi..., V&l Vf V into k < 20/²² classes such that irrega S Here, e. a universal constant that does not depend on G Gadd..
The weak regularity lemma states that any large graph G can be approximated by a weighted graph Ge with node V (Vi...., V& The nodes of G represent clusters of nodes from G, and the edge weight between two clusters V. and V, is given by (V(, In this context, an important TVi1D,,
property of the irregularity (Pre is that it can be seen as the cut metric between the G and
SBM based on G For each node i denote by V4. P the partition set that contains the node. Given
G construct a new graph G' with nodes, whose adjacency matrix A (/ is defined by
of, = ecc(V Vos)
Let A be the adjacency matrix of G. can be shown that
||A- A irrega (P),
which shows that the weak regularity lemma can be expressed in terms of cut norm rather than irregularity.
C GRAPHONS AND NORMS
Kernel. A kernel Y is measurable function Y [0, [-1,1].
Graphon. graphon [Borgs et al. 2008 Lovász 2012) a measurable function W [0, 1] - [0, 1]. A graphon can be seen as weighted graph, where the node set is the interval [0, 1j. and for any pair of nodes x, y E [0, 1]. the weight of the edge between x and y is W (z, y). which can also be seen the probability of having edge between and y. We note that in the standard definition graphon is defined to be symmetric, but we remove this restriction in our construction.
Kernel-signal and Graphon-signal. A kernel-signal is pair (Y, where Y is kernel and y [0, 1] R is a measurable function. A graphon-sight -ignal is defined similarly with a graphon in place of kernel.
17

---

Published as a conference paper at ICLR 2026
Induced graphon-signal Consider interval equipartition In. (II...., Im) ). a partition of [0, 1] into disjoint intervals equal length. Given a graph G with an adjacency matrix A, the induces graphon WA is the graphon defined by W Wa(z, y) A [am]] Tum where we use the convention that [0] 1. Notice that W piecewise constant function on Im Im As such, graph of m nodes can be identified by its induced graphon that piecewise constant on Im Im
C.I WEIGHTED FROBENIUS AND CUT NORM
Weighted Frobenius norm. Let q [0,1] (c, xo) be measurable function in - ( ([0,1)²) 1J²). where c 0. We call such a weight function. Consider the real weighted Lebesgue space ((0, 1)2:q) q) defined with the inner product
(X, (X, = 1| JI p.11 Y(x, ((x,)))(( () y)dzdy,
where 1 is the constant function [0, 1ja (x, and ||]| - Jf q. When & 1, we denote
(X, Z) = (X, Z)1- Let B B > 0. Consider the real Hilbert space ( :2: x (I (I. 1)) defined with the weighted inner product
((Y, v),
(),,),,"" (V', ,2)) = (Y')))(Y' vl
1 "'Illl // aa. ((a, (g(l,,)).a....))))).)))) v)drdy
8 12 D
Σ /
y (z)x)/
j=1
[0.1]
We call the corresponding weighted norm the weighted Frobenius norm, denoted by
8
I(Y,2))l = II(Y, v) 1l
|||
lus
lF
D
f=1
where | (,, and || (Uj 15)1
Similarly, for a mitrix- we consider weight matrix Q E [c, NON D,D' E R NxN, define the weighted inner product by
where > 0. For
(D. = 11l1
Σ s.jE[N
dr.di
where E NxN is the matrix with all entries equal 1, and weighted matrix-signal Frobenius norm by
|11.
Eise(Ni> Pig- Define the
8 D
()l,2)llr || Z) 11:
a:
a
Σ
|
where |DI| l (D, Q and ||= (zj, 21)1
Graphon weighted cut norm and cut metric. norm
Define for kernel-signall (Y. y) the weighted
sup / / Y Y (z,,))((s, ()) yddddy +B (IXY = [IYY, II [
1
1 (x))d
Σ
sup u
u.V
D
j=1
where the supremum is over the set of measurable subsets 44 [0.
The weighted cut metric between two graphon-signals (W.f) and (W", is defined to be IIW, f) (W', "W'lll)
18

---

Published as a conference paper at ICLR 2026
Graph-signal weighted cut norm and cut metric. Define for matrix-signal (D, (), where D E and Z E RND, the weighted cut norm
[ID,, 2) II(D, 11o. = a D DIlao + 2
a
ΣΣ d5.9 REM JEV
B
Σ Z1,j
max U.VEIN]
+
max
DN
UCIN
NEN
The weighted cut metric between two graph-signals (A.s) and (A',s') is defined to be (),,s) (A', s'). We note that this metric gives meaningful notion of graph-signal similarity for graphs as long as their number of edges satisfy || OE)) All graphs with E < || have distance close to zero from each other, so the cut metric does not have a meaningful or useful separation power for such graphs.
The weighted cut-metric between two graphs A and A' represents the maximum (weighted) dis- crepancy in edge densities of and A' across all blocks, giving the cut-metric a probabílistic interpretation. For simple graphs A, AA, the difference A - A' is granular function with values jumping between -1, and In such case l norms of A A' tend to be large. contrast, the fact that the absolute value in ① is outside the sum, unlike the & norm, results in averaging effect, which can lead small distance between A and A' in the cut distance even if A A' is granular.
Densifying cut similarity. In this paper, will focus special construction of weighted cut norm, which we construct and motivate next.
In graph completion tasks, such link prediction knowledge graph reasoning, the objective is to complete a partially observed adjacency matrix. Namely, there is a set of known dyad M C [N]? and the given data is the restriction of A the known dyads
AlM M - 1).
The goal is then to find an adjacency matrix B that fits A on the known dyads, namely, Bl F AlM- with the hope that B also approximates A on the unknown dyads due some inductive bias.
Recall that & denotes the set of edges of A. We call g = [N] \ E the set of non-edges. The training set in graph completion consists of the edges n AM and the non-edges 8 n M. Typical methods, such as VGAE (Kipf & Welling 2016) and TLC-GNN (Yan et al. (202I), define a loss of the form
I(B) = Σ
Cn (Un,m, an.m) +
Σ
Cn,m th2 (bn,ms an.m)s
(N.m)EMDE
(n.))EMnes
where 4h, 1/2 : R22 + R are dyad-wise loss functions and Cn,m E R. are weights. Many methods, like RotateE (Sun et al. 2019). HousE (Li et al. 2022a) and NBFNet (Zhu et al. 2021), give one weight mm. = C' for edges (n, m) E E and a smaller weight cn,m = c < C' for non-edges (n,m) E E n M. The motivation is that for sparse graphs there many more non-edges than edges, and giving the edges and non-edges the same weight would tend to produce learned B that does not put enough emphasis the connectivity structure of A. In practice, the smaller weight for non-edges is implemented implicitly by taking random samples from M during training, balancing the number of samples from & & and from 8 N.M. The samples from & NM are called negative samples.
Remark C.1. In this paper we interpret such an approach as learning a densified version of A. Namely, by putting less emphasis non-edges, the matrix B roughly fits the structure of A, but with a higher average degree.
Motivated by the above discussion, we also define a densifying version of cut distance. Given a target unweighted adjacency matrix A = (a.., ) =ij=1 to be approximated, we consider the weight matrix Q =e + (1 (1-66 e) for some small and being the all matrix. Denote the number of edges
'The asymptotic notation a, (bbx) means that there exist positive constants C1, C2 and no such that c1b, S on 5 cghn for all m 2 no- In our analysis, we suppose that there a sequence graphs with N, nodes, F,, edges, and weight matrices Qn-
"A dyad a pair of nodes (m,n) n) E [N]² For simple graph, a dyad may he edge or non-edge.
19

---

Published as a conference paper at ICLR 2026
by E = |E). Next, would like to choose to reflect some desired balance between edges and non-edges. Since the number of non-edges is N2 E and the number of edges E, we choose in such way that (E/N²)e TE/N2 for some I >> 0, namely,
TE/N2
e EET
(11)
(E/N2)
The interpretation of T is the proposition of sampled non-edges when compared with the edges. Namely, the weight matrix Q = e e effectively simulates taking I'E negative samples and E samples. Observe that
E/N2
Σ 0i,ji = | |||| ((1--)))) EIJENN 9i [.jENN?
e (1 (1-e) = 1/(T + 1).
To standardize the above similarity measure, we normalize it and define the weighted Frobenius norm (1+I) B and weighted cut norm (1 (1+1)) Bllo: where
Q^ = QA. = eg.r
Cg.r)
(12)
and where eg,r defined in II We now have
(1 (I+ || =1
(13)
This standardization assures that merely increasing in the definition of the cut metric (1 T) A| B B would not lead to seemingly better approximation. The above discussion leads to the following definition.
Definition C.1. Let A E (0, 1)NNN be unweighted adjacency matrix, and T > O. The densifying cut similarity between the target A and any adjacency matrix B NNN is defined to be
( = o0. = (1+ r) ||A Blln.a
where QA is defined in 12). Given a, 3 > 0 such that a + 3 1, the densifying cut similarity
between the target graph-signal (A, X) and the graph-signal (A',')) X') defined to be
(AA, (AA, X')) = 0.0.3,r ((A, (A,X))((A x')) = a B + 3 X ll
We moreover note that the similarity measure on ( B) is not symmetric, and hence not a metric. The first entry A in (A(ABB) interpreted the thing be approximated, and the second entry B as the approximant, Here, when fitting an IBG to graph, A is a constant, and B is the variable.
D PROOF OF THE SEMI-CONSTRUCTIVE DENSIFYING DIRECTIONAL SOFT WEAK REGULARITY LEMMA
In this section we prove a version of the constructive weak regularity lemma for asymmetric graphon signals. Prior information regarding cut-distance, the original formulation of the weak regularity lemma and it's constructive version for symmetric graphon-signals can found in (Finkelshtein et al. 2024a Appendix A, B).
D.1 INTERSECTING BLOCK GRAPHONSS
Below, we extend the definition of IBGs for graphons. The construction is similar to the one in Appendix B.3 of Finkelshtein et al. (2024)), where ICGs are extended to graphons. Denote by x the set of all indicator functions of measurable subset of [0, 1]
= (1. C j0, measurable).
Definition D.1. A set Q of bounded measurable functions q [0, 1] + B. that contains is called soft affiliation model.
For the case of node level graphon-signals, use the following definition:
20

---

Published as a conference paper at ICLR 2026
Definition D.2. Let D N. Given soft affiliation model Q. the subser [ of of (L) of all elements of the form (eu(x))(()) bu(z) + co(2)), with u, E Q R and b E RD is called the soft rank-1 intersecting block graphon (IBG) model corresponding to Q. Given K E N, the subset [2) of T.2 (0, 1J2 (1, 11) of all linear combinations of K elements of [2] is called the soft rank-K K IBG model corresponding 2. Namely, (C,p) [2] k and only if it has the form
C(2.0) v) = Σ (xxux())ok()) and p(z) = 1=1
Σ (x)x(2) ccuu(()
where (u=) QK are called the target community affiliation functions, (Ux ) QK called the source community affiliation functions, (ax) E R are called the community affiliation magnitudes, (bx (6x) Ig are called the target community features, and (c*) k== R the source community features. Any element of [Q] called an intersecting block graphon-signal (IBG).
D.2 THE SEMI-CONSTRUCTIV WEAK REGULARITY LEMMA HILBERT SPACE
In this subsection we prove the constructive weak graphon-signal regularity lemma.
László Miklós Lovász (0077) extended the weak regularity lemma graphons. They showed that the lemma follows from a more general result about approximation in Hilbert spaces the weak
regularity lemma in Hilbert spaces (László Miklós Lovász 2007 Lemma 4). We extend this result to have a constructive form, which we later use to prove Theorem 4. For completeness, we begin by stating the original weak regularity lemma in Hilbert spaces from (László Miklós Lovász 2007).
Lemma D.1 ((László Miklós Lovász, 2007)). Let K K2,... be arbitrary nonempty subsets (not necessarily subspaces) of real Hilbert space H. Then, for every m S [1/e2] and (fi E K,,) and (7s E R) such that for every E Kmm+1
and g E H. there is
K w.g-
>
rifi)
S ||w||| ||911
Finkelshtein et al. (2024a) introduced version of Lemma D.I (Lemma B.3 therein) with "more constructive flavor." They provide a result which the approximating vector > 74 is given as the solution to "manageable" optimization problem, whereas the original lemma in (Lászlö Miklós Lovász 2007) only proves the existence of the approximating vector. Below, we give similar result to (Finkelshtein et al. 2024a Lemma B.3.), where the constructive aspect is further improved. While Finkelshtein et al. (2024a) showed that the optimization problems leads to an approximate minimizer in high probability, they did not provide way evaluate if indeed this "good" event of high probability occurred. In contrast, we formulate this lemma in such a way that leads a deterministic approach for checking whether the good event happened. In the discussion after Theorem D.2, we explain this in detail.
Lemma D.2. Let bKG be sequence of nonemply subsets of a real Hilbert space H. Let K e N, 6 2 0, let R 2 1 such that K/ K/Re E 14, let 8 > 0, and let E H. For every k E N, let
7 (1 + 5) inf 9
Σ
kyhill
k.h
where the infimum is over k = {Ki,..., kR E & and h = (hr, ......,,) E EG x... x Krp. Then,
1. For every E N, any vector of the form
9" Σ Jass such that y= - E R
and (= EKi X...... (14)
1=1
that gives a close-to-best Hilbert space approximation of g in the sense that
1|g g"ll S Tmm
(15)
also satisfies
Vw E Km+H1
(w,, g - g²)l S ||l|||
V 7m
7m++1
(16)
1 -
21

---

Published as a conference paper at ICLR 2026
2. If m is uniformly randomly sampled from [K]. then in probability 1 (with respect to the choice of m).
||wll VTl
7mm-1
|
I191l
8
R(1 +
(17)
1
K
Specifically, probability 1 t. any vector of the form 14
which satisfy (5).
also satisfies
R(1 + 5) 8
Vw E Km+1, k(,g 9")l S ||=/| 1e9l V
(18)
K
The lemma is used as follows. We choose m at random. We know by Item that in high probability the approximation good (i.e. (18) is satisfied), but we are not certain. For certainty, we use the deterministic bound (16). which gives certificate for a specific m. Namely, given realization of m, we can estimate the hight-hand-sin
of (16), which is also the left-hand-side of the probabilistic bound (17). For that, find the (m + 1)" I'th error 1m solving another optimization problem, and verify that (17 is satisfied for m. it is not, we resample m and repeat. The expected number of times we need to repeat this until we get small error is R/(R- 1).
Hence, under an assumption that the we can find a close to optimum llg - gell for a given m in Tk operations,
find in probability vector g in the span of Ki.-.., KN that solves (18) with expected number of operations T Rt/ (R (R. 1).
Proof of Lemma D.2
Let K > 0. Let R 2 such that K/R R E N. For every k, let
Tk (1 + 8) inf 1g
kyhill
where the infimum over K {Ki, Ks} E l and {hi,..., hx} E KG x... Kc..
Note that every
m g"
9sfs
(19)
j=1
that satisfies
11g - g²1l²
S 7m
also satisfies: for any w E Km+1 and every E R.
llg - (g" + tw)ll 2
Mm+1
Mm + 7m-1
Bm
11g 99"
7m 7m
1+8
1+0
1+8
1+0 8
This can be written as
Vt e R, || 12 (w. g 9²) t Mm Mm+
(1
1
11g 9-11 0. (20)
1 1+
1 8
The discriminant this quadratic polynomial is
4 (w.gg g g² ||m|| (mm 7m
1 1 l1g 0²1(2)
1+8
and it must be non-positive to satisfy the inequality
(20). namely
4 (w,g
g²)² < ||
7m
7m+1
+(1
1
5 llg 9 gr1l3) || (Tm
7m - 7m+11
+(1
1
8 )mm
1+0
1+
1+
4 ||ull (m
mm++1
1 1 8
which proves
1w, g - --") ||ol| V
7m++1
7m
1 8"
which proves Item 1
22

---

Published as a conference paper at ICLR 2026
... 2 0. Therefore, there is subset of at least R(1+5) (1 #) +1 indices m in [K] such that 7m S 1m + *- K ||91l Otherwise, there are π indices
For Item 2 note that ||g|l 2 2h
148
K
m in [K] such that 7m
< 1m
n(1+6)
l which means that
K R + 6)
1g| S (1+ + 5) 1191 (1 6) 1191 O.
7KK 71
R
which is contradiction to the fact that nK 2 0. Hence, there is set M S [K] of (1 1/ K indices such that for every m E M,
|l|| V 1m
7m+11
||l||
Mm+11
R(1 8)
1m++1
1
K
+ 8
18(1 + 6)
R(1 + 8)
||m||
V 1 7m++ +
|1911 I ||w/| V 6 111111 +
K ||911
K
R11 -(1+8)) 8)
= 119l
66+
K
D.3 THE DENSIPYING SEMI-CONSTRUCTIVE GRAPHION-SINNAL WEAK REGULARITY LEMMA
Define for kernel-signal (V the densifying cut distance
1 I. / ((x,,))((, 3 IVV,f)lo II u.V
Σ sup
sup
D
U
Below we give a version of Theorem for intersecting block graphons.
Theorem D.3. Let (W be a graphon-signal, K E N. > O, and let Q be a soft indicators model. Let q be weight function and a, B 0. Let R 2 such that K/R N. Consider the graphon-signal Frobenius norm with weight [I(Y, y) P:gg = [[Y. y) Vll and cut norm with weight
II(Y, == |I(Y, y) V For every l E N, let
? (1 + 8)
II(W,s (C, (C.p)el@)k
inf
Then,
1. For every m N, any IBG (C*,p" pp) E [2]m that gives close-to-best weighted Frobenius approximation of (W, s) in the sense that
II(W,) (C" (C",,"))l',, < 7/m
(21)
also satisfies
() (0" (C" -WW.s)-OOr,p')lel (Va+ vB) Tm
7m+11 1+
2. If m is uniformly randomly sampled from [K], then in probability choice of m),
1 (with respect the
7m-1 S ValWiP. + B1
R(1 11+ +)
Am
(22)
1
Specifically, in probability
1.- any (C",p") [2)m which satisfy
21
also satisfies
([ (C*, 10)0000 S (Va+ vB) (V)llW/ + 5
R(1 + 8)
(23)
23

---

Published as a conference paper at ICLR 2026
Theorem D.3 is similar to the cemi-constructive weak regularity lemma of Finkelshtein al. (2024a Theorem B.I). However, our result extends the result of Finkelsheein et al. (2024a) by providing deterministic certificate for the approximation quality, explained in the discusson after Lemma (D2 extending the cut-norm to the more general weighted cut norm, and extending to general non-symmetric graphons.
Proof of Theorem D.3 Let us use Lemma weighted inner product
D.2 with H = L2 x (L310, 1)) with the
((V.)), (V', ,))),, |1lll S
+ +B E
J Jo.1 ys (z)2)/())dz
and corresponding norm denoted by |I(Y, ((Y,))llex v |Y Fl + +3E IMs and Kj 1 Note that the Hilbert space norm is the Frobenius norm in this case. Let m E N. In the setting of the lemma, we take g (W; s), and 9" [2]m- ma By the lemma, any approximate Frobenius minimizer (C",p" namely, that satisfies [[(,, s) (C*,p") ,p'))l I fmm also satisfies
((T.
(W, (W,
(C*, ,p""''' ,)²)), s [I y)ll 7m
7m
1
for every (T,y) (2).
Hence, for every choice of measurable subsets S,T C [0, 1]. we have
(z, - C* (x, v)) y) dxdd
1:g
((Ls @ L7,
(C" ,p')),)))))
(1s IT, 0)llma Tm
7m+1
1
S Vay 1m
1mm+1
1 5
Hence, taking the supremum over S, T C [0, 1], we also have
a - -C*Ilng Vo nm
7m-1 1+5
Now, for randomly uniformly sampled from [K], consider the event M (regarding the uniform choice of n) of probability (1 1/R) in which
7/
S V WallWIB
B. +
R(1 + 8) 5+
1h
1+8
K
Hence, the event M, we also have
R(1 + 5) K
W - C* 1r S W + +1Bl1ally
Similarly, for every measurable T [0, 1] and every standard basis element b (8,,)) for any j E [D].
/ (s)(x) -2)()))
7
1
((0, bll)., -
3
(00, bl bl
1m
Dm+1
1 1
VB
7m
7m
1 82
24

---

Published as a conference paper at ICLR 2026
so, taking the supremum over T C [0. 1] independently for every E [D], and averaging
j E [D]. we get
B I|s - p- Ia 2 v 7m
11+1
1 0
Now, for the same event M above regarding the choice of n E [K],
R(1 +
8 - - o - VaslIWIP :F:, + 8 ||
K
Overall, we get for every m and corresponding approximately optimum (C*, (C*,p"),
(WW (C*,,"")ll pm)) $ (Vá+
v Tm 1 1+0
7m+1
Moreover, for uniformly sampled n E [K], in probability more than 1/R,
II(W,) -C" (C",,"")llxx" S (Va + (ValWa/ +B11slBe
R(1 + 6) 6
K
D.4 PROOF OF THE SEMI-CONSTRUCTIVE DENSIFYING WEAK REGULARITY LEMMA
Next, we show that Theorem D.3 reduces to Theorem in the case of graphon-signals induced by graph-signals.
Theorem 4.1, Let (A, X) be a graph-signal, K E N. 8> O, and let Q be a soft indicators model. Let a. 3 > O such that a 3 = 1. Ler > 0 and let QA be the weight matrix defined in Definition 3.2
Let R 2 such that K/R. R E N. For every k N, let
n = 6)
min (C.P)
[IA, - (C, P)llr..aaaa(
Then,
1. For every m E N. any IBG (C',P") [Q]m that gives a close-to-ber weighted Frobenius approximation of (A, X) in the sense that
X) (C*,P") P"))).e S 7ms
(24)
also satisfies
3.r (II(") S (V VBV ym
Mm++1
(25)
1
2. If m uniformly randomly sampled from [K], then in probability choice of m))
R (with respect the
V VTn 1+8 $ 18+ R(1 R(1+6)
Mm+1
(26)
Specifically, in probability 1- R. any (C*, P') E [Q]m which satisfy 24 also satisfies
D (aar((AA (A, PC), s (V2+T) R(1 + 8)
(27)
K
In practice, Theorem 4.1 is used to motivate the following computational approach for approximating
graph-signals by IBGs. We suppose that there is an oracle optimization method that can solve (24)
in T' operations whenever m < K. In practice, we use gradient descent on the left-hand side
of (24) which takes OEE) operations as shown in Proposition 4.2 The oracle is used as follows.
We choose m E [K] at random. We know by Item 2 of Theorem 4. that in high probability the
good approximation bound (77 is satisfied, but we are not certain. For certainty, we use Item Tf
Theorem 4.1 Given our specific realization of we can estimate the right-hand-side of (25) by our oracle optimization method in 2Tx operations, and verify that the right-hand-siee
(25) is less
than the eight-had--se
of (7). If it is not (in probability 1/ RR), resample and repeat. The
expected number times we need to repeat this process until we get a small error is R/ (R 1),
the expected time it takes the algorithm to find IBG with error bound (2 is 27 K R/ R 1)-
25

---

Published as a conference paper at ICLR 2026
Proof of Theorem 4.7 Let QA be the weight matrix defined in 12 Consider the following identities between the weighted Frobenius norm of induced saphonn-iignlle and the Frobenius norm of the graph-signal, and, similar identity for the densifying cut similarity.
[WW.. - (We. Wp a(tt)) - (A (C, Pilli.aaaattn (28)
L,a, (WW (Wa, 8, 8x))
- a,, ( (AI,)
We apply Theorem D.3 on the weighted Frobenius and cut norms with weight Q = We.- We
immediately obtain from (88) For (26 by (22 of Theorem D.3 and by (13) and by the fact
that signals have values in
11 II.
Mm++1 mm
R(1 + 8) S Va((1 + W))lWall?s + +111aA 8
1 1+ 8
K
R(1+8)
K
Lastly. 27 follows the fact that for a, 3 > such that + 3 1, we must have (Va(1 +1)
VB) V
E FITTING IBGS TO GRAPHS EFFICIENTLY
Below present the proof of Theorem 4.2 The proof follows the lines of the proof of Proposition 4.1 (Finkelshtein et al. 2024a). We restate the proposition below for benefit of the reader.
Proposition 4.2 Let A (atr) 1 be an adjacency matrix of an unweighted graph with E edges. The graph part of the sparse Frobenius loss can be written as
A - U diag(r)
|AAlF + (1+T)E
Tr ((V V) diag(r)(U diag(r)) diiag(r))))
F:QA
2
Σ
U diag(r) (VT) Dz,j
(1+T)E i=l JEN(()
1-
Σ 1=1 JEN(()
EV,, (U., diag(r) (VT)..))
where QA is defined in Equation 2 Computing the hight-hand-side and its gradients with respect to U. V and r has time complexity of OKK2N + KEE,, and a space complexity of O(KN + E).
The proof is similar to that of Proposition 4.1 in Finnellshtein et al. 2024a), while applying the necessary changes under the new weighted Frobenius norm and the structure of IBGs.
Proof. The loss can be expressed
|| A - U diaggr))
Σ jEN(E)
ai,j U diag(r) (VT)..)) )² +
(1+
+ Σ (-U diag(r) (V (-ig.)ia(r))
(VT)..)
(EN())
N
Σ
ais U,, diag(r) (VT) )²
>e U diag(r) (VT)..) )²
E
[
JEN(()
j=l
Σ (U..g(r)))) (VT)..)
JEN(6)
26

---

Published as a conference paper at ICLR 2026
We expand the quadratic term (ais Ui diag(r) (VT) ) and get
A U diag(r)) FIQA
Ug diag(r) (VT)..) +
(1+T)E
(03s 20 diag(r) (VT).. ).s 0n.)
(1+T)E (E)
1-e Σ Σ
( diag(r) (V)).)) )²
(1+1)
JEN(()
eN2
UU diag(r)
(1+1) E
N
N
Σ
2
Σ
Σ jEN(()
U diag(r) (V 04,
(1+T)
(1+1)
E
i,==1
i=1
N
+ (1+T)
Σ
U diag(r) (V )
i=1 jEN(
Tr (V V diag(r)U U diag(r)) +
(1+D)E E
N
||||
(1+ T)
N
Σ im jEN(()
U diag(r) (VT). aitt
(1+ T) F
N
1-c (1 (1+T) (EN()
Σ
(U diag(r) (VT) )²
Here, the last equality uses the trace cyclicity, i.e., E TH(IJT)= = =Tr(JT I), with V diag(r)U U diag(r) and J V
To calculate the first term efficiently, we can either perform matrix multiplication from right to left or compute U U and V V, followed by the rest of the product. This calculation has time complexity of N) and a memory complexity O(K N(NN. The second term in the equality is constant and, therefore, can be left out during optimization. The third and fourth terms in the expression are calculated using message-passing and thus have time complexity of OKE)). Overall, we end up with a complexity of N K) and space complexity of O N + E) for the full computation of the loss and its gradients with respect to U, V and r.
F EXTENDING THE DENSIFYING WEAK REGULARITY LEMMA FOR SOPHON-EDGE-SIGNALL
In this section we prove a version of Theorem D.3 for the case where the graph has an edge signal. The proof is very similar to the previous case, and the new theorem can be used for the analysis of IBG-NN when used for knowledge graphs (see Section D.
F.1 WEIGHTED FROBENIUS AND CUT NORMS FOR GRAPHON-EDGEESIONAAL
Graphon-edge-signa A graphon-edge-signe is pair (V,Y) where V is graphon and Y: 00, 1]2 + R is a measurable function.
27

---

Published as a conference paper at ICLR 2026
Weighted edge-signal Frobenius norm Consider the real Hilbert space (10, x (L2(0,1)3) 1)3) defined with the weighted inner product (VVY), (V', r') ((V.Y). g00=
= | [T112ag 11 10,1j
V(a, Va,, (),(( v)dady
D D
B
Σ
I1 Yd (x, vddrdy.
We call the corresponding weighted norm the weighted edge-signal Frobenius norm, denoted
8 ΣΣ 1 D
II(V = [IVV Y Y)ll Fag.as a allVIlEs
We similarly extend the definition of a graphon weighted cut norm and cut metric.
Graphon weighted cut norm and cut metric. A kernel-edge-signal (V, Y) is pair where V [0, - [-1, and Y : [0, 1J² + Rº are measurable. Define for kernel-edge-sigee (V, Y) the weighted edge signal cut norm
/ V(a, v)g(a, v)drdy
II(V, IVV, 11 II(
sup U.v
I1ll
1
/ Y5kx, vidrdy u.v
sup
D
Jv
where the supremum is over the set of measurable subsets U1 V c [].
The weighted edge signal cut metric between two graphon-edge-signals (W, and (W", f') is defined to be (WW (W', I')lo
For simplicity's 's sake, and for this section only, we refer the weighted edge-signal Frobenius and cut norms simply as the weighted Frobenius and cut norms.
F.2 IBGS WITH EDGE SIGNALS
Here, we define IBGs for graphon-edge -dge---dgeeegeedeee signals. We use the same terminology of soft rank-K IBG model introduced in Definition slightly changing the signal part of the graphon.
Definition F.1. Let D E N. Given a soft affiliation model Q, the subser [Q] of 2 1 (L?(0, 1)3) of all elements of the form (au(x)v(y)) bu(z)u(w)), with u E Q a E IR and b E I is called the soft rank-1 intersecting block graphon (IBG) model corresponding to Q. Given K N, the subset [Q]x of L [0, 1|2 x (0, 1|2) of all linear combinations of K elements of [Q] is called the soft rank-K K IBG model corresponding to Q. Namely, (C,p) E { k if and only if it has the form
K
K
C(r,y)= = Σ (IuL(I)Ve()) and p(x, = E R=1
byun (a)u
k=1
where (m QK are called the target community affiliation functions, (ww) E QK are called the source community affiliation functions, (ax) E R are called the community affiliation magnitudes, (bx) K are called the edge features. Any element of [Q) k is called an intersecting block graphon-signal (IBG).
We emphasize that for the rest of this section, when referencing weighted Frobenius and cut norms, as well as the soft rank- K IBG model, we refer to the new definitions as formulated Section F Corollary F.1. Let (W, be a graphon-edge-siee model. Let q be weight function and a, B 0. Let 2 such that K R N. Consider the graphon-signal Frobenius norm with weight [I y) v) = (Y, v) 1ig..aa. and cut norm with weight II(Y,))ll: [I V) For every is E N, let
K E N, 8 > O, and let Q be a soft indicators
7 (1 + 8)
[I(W,s (l (C.p)
inf
Then,
28

---

Published as a conference paper at ICLR 2026
1. For every N, any IBG (C", ,p)p") [2]m that gives close-to-best weighted Frobenius approximation of (W,s) s) in the sense that
I(W, (C", (C",,")llE, S 1mm
(29)
also satisfies
I(W,s) (C" (C", (Va+ vB) Tm
7m+1
1
2. If m is uniformly randomly sampled from [K]. then in probability choice of m),
H (with respect to the
Mm
7m-1 1
V /l + + B1 8+
R(1 +1
(30)
K
Specifically, in probability 1 - #.. any (C*, E 12 which satisfy
29
also satisfies
I(W, 8) - (C",,"))Ilww" S (Vā+ (Volwil + 3 | 8
R(1 +
K
The proof is very similar to the original proof, with a slight adjustment for the analysis of the signal part of the graphon-signal. For completeness of the analysis, we provide the full proof.
Proof. Let us use Lemma D.2 with H = T22 x (T,7 1}3) with the weighted inner product
(V,Y),,V,, Y"), |1111: Jfon V(,,)) ydxdy
+
|1112:g 10.11" ((, v)) V)g(2, v)drdy.
and corresponding norm denoted by II(V ValIVIE E [ F:y" and K, [2]- Note that the Hilbert space norm is a weighted Frobenius norm. Let m E N. In the setting of the lemma, we take g (W,s), s), and g" [Q] m- By the lemma, any approximate Frobenius minimizer (C*,p) p"), namely. that satisfies [[(W, s) (C*, (C',p"'" >'"")lF I Mm. also satisfies
((T.)) (W,,) (C", .p )) $ (TT all Tm
7m
1 1+
for every (T, [Q]. Hence, for every choice of measurable subsets S,T [0, 1], we have
(W Ca (x.,))((E drdd
1:g
((1s @ 17, 17,0), (W, (C",,")))
[1(ss @ Lr, 17,0)lleay 7m
7m+1
1+0
1 Vāl
Mm+1
Tm 1
Hence, taking the supremum over S, T C [0, 1]. we also have
a ||W - C* C* lm: vay 1m
7m-1
1 1+0
Now, for randomly uniformly from [K], consider the event M (regarding the uniform choice of n)) of probability (1 1/ R) which
nn
1n+1
1 < Vallw P + +
8
R(1 + 6)
K
29

---

Published as a conference paper at ICLR 2026
Hence, in the event M, also have
R(1 6)
W - 1l S W + 0 ||
K
Similarly, for every measurable S, T [0, 1] and every standard basis element (6 for any
j E [D].
1 (s(x, - p" p==,,,""//0>>> (o,,))(a,, wdddy
1 (0, @ (W, (C", (C))
3 (1.0, b(ls @ 1T)llE 7m
7m+11
1 8
$ 3
1
v 3 9m 1+6
1m+11
taking the supremum over S, T C [0, 1J, independently for every j E [D], and averaging over j E [D]. we get
| - 10-p"1l r' S /VB VBV Tm
7m+1
1+
Now, for the same event M as above regarding the choice of n
E [K].
8 R(1 + 6)
8 -|ls->'ll= - Va81/WIRP Pr 82 || Overall, get for every and corresponding approximately optimum (C" .p)pp"
K
(W: s) (C", l') I (V Tm 1 +
7m+11
Moreover, for uniformly sampled E [K], in probability more than 1/R,
((W - (C* """,""") (Va+ /B) (VallwI,, + 311e1le
/ R(1 +)
K
G INITIALIZING THE OPTIMIZATION WITH SINGULAR VECTORS
Here, we propose good initialization for the GD minimization of We explain how to use the SVD of the graph to initialize the parameters of a rank K-IBG, before the gradient descent minimization of Equation ( This is inspired by the eigendecomposition initialization described of ICGs. The full method is presented in Section G and summarized here.
We begin by caleulating the K/4 / SVD decomposition of the graph adjacency matrix. Denote by Ø//4 = (ax)
K/4 the sequence of the K/4 largest singular values of A, and by $ K/4 (Φ+)
K/4
K/4 (ab))
K/4 their corresponding left and right singular vectors.
For each singular value and corresponding singular vectors Φ 2b d+ $
we designate
d+
T++ I T [ as target communities, and { [ Th Tw T the corre-
+++ sb *
1b
|
sponding source communities, where & E [0, ) denotes the positive or negative parts of the vector E, i.c., E E E_. The corresponding affiliation magnitudes are then taken be
r = a || 1l.o || Il 12 = a || ol 1lao
r3 || al 11 1' || 11 1
K is not divisible by 4, we discard the excess components with the smallest community affiliation magnitudes in absolute value.
To efficiently calculate the leading left and right singular vectors, we may use power method variants such the Lanczos algorithm (Sadd 2011) simultaneous iteration (Trefethen & Bau 2022) in (EE) operations per iteration. For very large graphs, we propose in Section G.2 a more efficient randomized SVD algorithm that does not require reading the whole graph into memory once.
30

---

Published as a conference paper at ICLR 2026
G.1 THEORETICAL ANALYSIS OF SVD INITIALIZATION
Next, we analyze this initialization and show that it attains relatively high initial accuracy. The following is corollary of the densifying weak regularity lemma with constant g(z,, y) F. the signal weight the cut norm set to 3 = O, using all measurable functions from [0, 1] to [0, 1] as the soft affiliation model, and taking relative Frobenius error with 5 = 0 on theorem D.3 In this case, according to the best rank- K approximation theorem (Fckart-Younl Young-Mirsky Theorem (Trefethen)
N²
& Bau 2022 Theorem 5,9)), the minimizer of the Frobenius error is the rank-K K singular value decomposition (SVD). This leads to the following corollary.
Corollary G.1. Let A be graph, K E N, let m be sampled uniformly from [K], and let R 2 1 such that K/R R E N. Let u1..... Um and UI....y Um be the leading left and right singular vectors of A respectively, with singular values Ji...., on of highest magnitudes Ø1 2 |02l 2... 2 |oml, and let C = Ik=1 OyURUK Then, in probability 1 (with respect to the choice of m).
R K
|| - C In In
Proof. Consider Theorem D.3 with d = 0,, = 0,I = 0, and taking the constant weight
N
((x, v) = E
Under this setting, the weighted Frobenius norm becomes the standard Frobenius norm, and the weighted similarity measure becomes the cut norm. Consider the induced graphon signals W and Wo.. Note that under the standard Frobenius norm, Wc- satisfies Equation (21). as Wc- is the
SVD of WA and is also the best Frobenius norm approximator. Hence, the bound in Equation 223 is satisfied in probability 1//R, and becomes
R [ We. Ila S [
K
We immediately get in probability 1- 1-RR
A - Ca < || V
K
as required.
The initialization is based on Corollary G.1 restricted to induced graphon-signals with densifying
cut similarity with a constant weight Pú N2/E. Consider UK/4 Ex/a VT
K/4 the rank K/A
singular value decomposition A. We get
N
4R K
| - CII
(31)
We note that while the lemma guarantees a good initialization for the graph, the goodness is not measured in terms of the graph-signal densifying similarity, but rather with respect to cut metric. Still, we find that in practice this initialization improves performance significantly.
It is important to note that the method described in the previous section relies computing the singular value decomposition (SVD) of the graph's adjacency matrix. Traditional algorithms for SVD require the entire adjacency matrix be loaded into memory, which can be computationally expensive for large graphs. Similar to the approach proposed for computing the IBG in Section aim to allow SVD computation without loading the entire edge set into memory.
In the following subsection, we introduce a Monte Carlo algorithm for computing the SVD of a matrix by processing only random small fraction of its rows, significantly reducing memory requirements.
31

---

Published as a conference paper at ICLR 2026
G.2 MONTE CARLO SVD ALGORITHM
For very large graphs, it is impossible to load the whole graph to GPU memory and estimate the SVD with standard algorithms. Instead, we propose here a randomized SVD algorithm which loads the matrix to GPU memory in small enough chunks.
The following theorem relates cigendecompossitinn of symmetric matrices SVD Trefethen & Bau 2022 Lecture 31).
Theorem G.2. Let A E RNXN with singular values σ1 2 ... 2 ON, left singular vectors
-1.-..y Uhi and right singular vectors v1....y UN- Consider the augmented matrix
0
A
B
A
0
Then, the eigenvalues of B are exactly o ON, ....... -0,, and the eigenvectors are all vectors of the form
= N.
(32)
2
uu;
Theorem G.2 is the standard way to convert eigendecomposition algorithms of symmetric matrices to SVD of general matrices. Namely, applies the eigendecomposition algorithm to the symmetric augmented matrix B, and reads the singular values and vectors from oI,..., ON, -ON and from 332
We hence start with a basic randomized eigendecomposition algorithm for symmetric matrices, based on the simultancous iteration (also called the block power method) (Trefethen & Bau 2022 Part V).
Given a symmetric matrix C, the standard simultaneous iteration (Algorithm I is an algorithm for finding the leading (largest in their absolute values) M cigenvector-cigevvalue pairs of C. We next replace the full matrix product CQ by a Monte Carlo method, initially proposed in (Drineas) IR N with columns Ci..... C2v E R and a column vector (...... UN) E R Let m. ..... my be chosen independently uniformly at random from [N]. Let us denote m (mi,... m) and
al. 2006). Consider matrix C
[Co)
Umy Cmyy
j=1
One can show that in high probability
[Culm 2 Cvu,
where the expected square error satisfies
[][[Cu) C0ll2 0(1J).
The advantage in the computation (Cu) is that reduces the computational complexity of matrix- vector product from ONN2) OJJN).
We hence consider a Monte Carlo simultaneous iteration algorithm, which is identical to Algorithm 1 with the exception that the matrix-vector product Z CQ is approximated by [CQ) m
Algorithm 1 Simultancous Iteration for Eigendecomposition of Symmetric Matrix
Input: Matrix C E RNN. number of leading eigenvalues to be computed M, number of iterations J.
Initialize Q RNNxMM randomly for i 1 to J do
Z Z=Q
(Q. R)
CeaeeeeddQQ---aaoiiiiiiiee Z)
end for
Compute À (A..... Aw) with X; Q[: CQ
Output: Approximate eigenvalues \ι, AM and corresponding columns UM of Q as the approximate eigenvectors.
32

---

Published as a conference paper at ICLR 2026
Lastly, we would like to the Monte Carlo simultaneous iteration algorithm for estimating the SVD of a matrix A via Theorem G.2 For that, we require an additional consideration. Note that the simultaneous iteration finds the leading eigenvalues and eigenvectors (up to sign) in case they are distinct their absolute value. In case X; * X but |^, = [Xyl, the simultaneous iteration would X; and >y. Now, note that Theorem
find vector in the span of the eigenspaces corresponding G.2 builds the SVD of A via the cigendecomposition of B. and every value X of B is repeated twice, with positive and negative sign (in case the singular values are not repeated), and Algorithm 2 finds vectors only in the span of the two eigenspaces corresponding to =λ₃ This is not an issue in the exact algorithm, as the singular vectors can be read off (32) regardless of the mixing between eigenspaces. However, in the Monte Carlo simultaneous iteration algorithm, the algorithm separates the two dimensional spaces of to one-dimensional spaces arbitrarily due to the inexact Monte Carlo matrix product. Moreover, the split of the space to two one dimensional spaces arbitrarily changes between iterations. Hence, when naively implemented, the SVD algorithm based on Theorem G.2 fails to converge.
Instead, we apply the Monte Carlo eigendecomposition algorithm on B + A1I, where X is the largest eigenvalue of B. computed by Monte Carlo power iteration B. Since the addition of X I shifts the spectrum of B by Å1. all eigenvalues of B become non-negative and distinct (under the assumption that the singular values of A are distinct). We summarize in Algorithm 2 resulting method (in the next page).
H LEARNING IBG WITH SUBGRAPH SGD
For passage-passiigg neural networks, processing large graphs becomes challenging when the number of edges E exceeds the capacity of GPU memory. For this reason, processing IBGs with neural networks, which take O(N) (N) operations, is advantageous. However, one still has to fit the IBG to the graph as preprocessing step, which takes (FF) operations and memory complexity. To address this, propose two sampling-based optimization methods for the IBG. The first method performs node sampling, extending the SGD approach of Finnellshtein et al. (2024a). The second samples individual entries of the adjacency matrix, which we refer to diodes. We term these methods node- sampling SGD and sammliig SGD, accordingly.
H.1 CONSTRUCTION OF NODE SAMPLING SGD
In a standard GD procedure, edges of the graph are loaded into memory. Instead, in our node- sampling SGD procedure, a set of M & N nodes is sampled uniformly with replacement from [V]. Denote these nodes by n = (nm ( We then perform the gradient step using the gradients calculated solely using these sampled nodes. More specifically, by denoting (n) IRM XM the
sampled subgraph with entries (i.j On,,,yy (n) E M the sampled sub-signal with entries
(n)
(n) Fn. and U(n) V(n) [0, 1JA as the sampled community target and source affiliation a;
(n) matrices with entries u ". = Uns, and (m)) = Un..j. The loss over the sampled nodes becomes:
a(1 + TT)
M
K
((M)(U()) r. r.F.
Σ
(UnnkkkUugkk - apnnnn 19nnn
M
1 1=
M
D
+
Unn + Unnkbbid an,.))?
MD
H.2 CONSTRUCTION OF DIODE SAMPLING SGD
We sample a set of M < 2 diodes D = (s. t) = (sm. tm )= independently from a distribution we define over all diodes of the graph. The probability of sampling diode (i, is (I+T)E.
45g and the
33

---

Published as a conference paper at ICLR 2026
Algorithm 2 Monte Carlo Simultaneous Iteration for SVD decomposition of Non-Symmetric Matrix
Input:
Matrix C E RNNN,, number of leading eigenvalues to be computed M, number of iterations J, sample ratio 0 < 1.
(Augment the non-symmetric matrix be symmetric)
0
C
Define B
C
(Leading eigenvalue estimation)
Initialize Q1 E R2Nx1 randomly
for i J do
Generate 2N r samples n of indices from [2N] with repetitions.
B B
Q: Q1(m [n. 1]
Z BQ: ReduccedQQR-Factoriiaaiin Z)
(Q1. R)
end for
A = Q BQ1
Shiift the spectrum of B}
B B 1d1l I2N
[Randomized simultaneous iteration on B)
Initialize Q p2N randomly
for i = J do
Sample vector of 2N indices from [2N] with repetitions.
B B n.
Q [n
BQ
(Q, R) Saaioeed-Q-Faattriztziii Z)
end for
(Generate the output)
Sample vector n of 2N r indices from [2N]] with repetitions.
B = B|: n
Q [n,
Compute (0I . MM) with or Q1:,]] [Q
Q. = 11 N..
Qu Q 2
Output: Approximate singular values d1..... om and corresponding columns ui...., Um and of Qu and Qu as the approximate left and right singular vectors.
Um U......
loss over the sampled nodes is
a(1+T) M
M
K
(M) (U,
(uem &.K Qsm dm )
We then perform the gradient step using the gradients caleulated solely using these sampled diodes. We note that for siode-sampling SGD, we define the loss only over the graph part. To perform SGD the signal part of the loss, the method is identical to node-sampling SGD.
34

---

Published as a conference paper at ICLR 2026
H.3 THEORETICAL ANALYSIS OF DIODE-SAMPLING SGD
In the following section, we prove that the gradients calculated using diode-sampling SGD with respect the sampled diodes approximate those calculated over the full graph using the standard loss in (8) Throughout the section we denote = 1/ Σ 95. and refer only to the sample loss of siode-sampling SGD.
Proposition H.1. Let 0 < 1. Consider the Frobenius loss weighted by Q, and B. we restrict all entries of U, V, and r to be in and E [M]
[-1, -1,1, 1), then in probability at least - p. for every l E [K]
2 log (1/p) + 2 2og K) - 2 log
V Unm, L
V
L L()
$ 2a (1 +11+111 +)A
M
2log(1/p) + 2 log(K) log(6)
Vingit Io
L(M)
2a +))
M
2 2log(1/p) + 21og K) 2 logg(6)
V L V (M))
S 20 +)
M
Theorem H.1
provide probabilistic bound on the difference between the gradients computed on full graph and those calculated using subgraph SGD. Notably, it shows that the gradients of the IBG parameters calculated with SGD closely approximate those calculated with standard GD.
We prove Theorem H.l by comparing the gradients of the full loss L with those of the sampled loss (M))
Consider the graph part of the IBG loss:
N
K
V.)
Σ
Σ
(uLereUjA ai.5)
kj=1k=
Next, we calculate the gradients of C U diag(r) V with respect U, V, and in coordinates. We have
Vre = Ui Ujkk
Nr Cij rrb:
and
where 6, is 1 if and zero otherwise. Hence, the gradients of the loss are
N
Lr = (o((1+)) +T)μ
Σ 4-=1
(c. - a..
N
V L = 1oa[1+1) + F)μ
Σ
(Cnu - an An.
i=1
and
V vn -= 2 + P)p
Σ
(ij,n ak.n)a..nkkk.....
j=1
Similarly
V LMM) 2a(1 I)
Σ
(Cas,t -ej,y,, )es, Noy
M
Uammk ((M) 20(1 P)p
M
(Cumdd - anmityy) T
M
35

---

Published as a conference paper at ICLR 2026
and
20x(1 + F) Cogg.mm Ogy, pm y
M
Umm (
M
The following convergence analysis is based on Hoeffding's inequality, and supporting Monte Carlo approximation lemma.
Theorem H.2 (Hoeffding's Inequality). Let ,....., Ym be independent random variables such that S Ym I b almost surely. Then, for every lo > 0.
c M
M
E[Ym)) 2 2k) S exp (- (b- a)-
2k M
We now Hoeffding's inequality derive standard Monte Carlo approximation error bound.
Lemma H.3. Let fimb 1 be uniform i.i.d in [N]. Let RN be vector with entries Un in the
sei -1,1, 1]. Then, for every 0 < p < 1, in probability at least 1 -
1 M
Σ
1 N
20o (1 1p)) + 2 1og((2)
2
M
m=1
Proof. This a direct result of Hoeffding's Inequality on the i..d. variables (vi... Jm=1-
We use Theorem
H.3 on the i.id samples m. We first show:
E [
[(M) V L,,
E V
L(MY]
V Wnm L,
and
B V Uaimac
LiM
V Vuamok L.
Indeed we have
2a(1 + r) E V (M)
M
El(Ca,,0, - ag Uu
M
20(1 + +)
M
E (Ca aay,t
M
j=1
N
2a + I)
Σ
P(s = j)(css ai, ai.))u,kUusk
sý=1
N
= 2a TT(
(Gr ai. (ey.).gu
1
2a(1 + D)
E V
L [(M]
B[(Cnmits amm Druue,
2a(11 + rT)
M
E (CCmm.d - Op (r
M
2a + +1)p
(Crmed anm Anmm TKU TKU j=1
Σ
36

---

Published as a conference paper at ICLR 2026
and
20((1 + r)
E V Fumii
Σ
TP (Crmiit - Onm )r
M
2a(1 + 1))
M
(Crmdd - (nkmdi)rk
M
j=l
N
= 2a + D)p
Σ
(Cnme) On 5 j.Ugk
This shows that the expected value of the sampled loss gradients is equal the standard loss's gradients, which meets the conditions of Theorem H.3 We therefore use the lemma to obtain probabilistic bound on the difference between the approximated gradients and the full gradients.
Specifically, for any 0 < < 1, for every k E [K] there is an event As of probability at least 1 P1 such that
2 2log(1 / /p1) 21og(2)
V Vr, (a0)
2a(a /
M
For any 0 < P2 < 1, for every E [K] there is an event U4 of probability at least 1 - P2 such that for every n E [N]
V un,, T V un [MM) S 2a + / (log(1/p2) + 1og((2
M
For any 0 < P3 for every n E [N]
1, for every [K] there is an event V4: of probability least 1 ps such that
2 log (/pa) + 2 log(22
V Mo L V Von. L(M)
< 220(a T
M
Lastly, given < p 1, choosing p1
13 p/3K and intersecting all events for all coordinates gives in the event & of probability at least 1
P2
Vr FaL-VVLine (an) 2a(a + /
2 2log(1 /pD) 2 log( K) + log(
M
2 2log (o/g1/p) + log (K) log(6)
Van V VeneeL (M)
< 2ala + +)
M
and
2 2log(1/p) + log(K) + 2 l6g(6)
V Vona V Vonne L(M) < <aa(a + +'y
M
proving Theorem
H.1
H.4 THEORETICAL ANALYSIS OF NODE SAMPLING SGD
In this section, we provide a similar result to the one in Section proving that the gradients calculated using node-sane sampling SGD with respect the sampled nodes approximate those calculated over the full graph using the standard loss in (8). Throughout the section we use the loss of node- sampling SGD.
HK
Proposition H.4. Let < < 1. Consider the Frobenius loss weighted by Q, a and B. If we restrict all entries of C. P. U. V, F and B be in [-1,1] 1), then in probability at least p. for every
37

---

Published as a conference paper at ICLR 2026
k E [K], d E [D]
and E [M]
M
log((1/)) + 22og(2N) + 2oo K) + 2 log 10)
Uum L
Unmm & L(M)
S 20((1 + T) V
N
M
M
(1g(11/)) 2og((N2) (og(() + log 10)
L
L I(M)
$ 21 + T)NN V
N
Um
M
2 + log( (N) 2 log [) + 2og (10)
VrL L
Vr (A0)
S 40 + D)NN2
43
2log(1/p) + 2lo + 2lg (D) + 2 log 10)
V Veia fr L (M0)
- DV
M
Vin.L Vi (M)
4,3
log(11p) + 2 log K) + log(D) + 2 log 10)
D
M
The proof of Theorem H.4 is similar to that of Theorem of the IBG loss
Define the graph part and the signal part
LU,, a(1 c(1+T)p
N
K
UHEETRUJ, (45))
N2
B
L.
ΣΣΣ (u.kfk.d + vibbbadd xt,d)?
ND
The IBG loss in is L N + L2. We normalize and multiply L1 by N2 for reasons that will become clear later.
Similarly, we define the graph and signal parts of the subgraph SGD loss
1 (U(())) v(n), r) a(1 H)
kTkkk - animn) 9m
M
(L)(()) ((n) F, where (M) 22
B MD
(Ung. + Ung - x)
+ (M
Next, we extend the calculations of the gradients of C U diag(r) V and P = UF VB with respect to U, V. r, F and B in coordinates. We have
V Se.Pi,d òi
Ve,,Pi.d v1,bd--d
V VaraPi.d = Ske,di--1
and
V Vi.PPid = bE.d8i-4
Hence,
a(1 + DD2
V
Σ
(cts - as a.,
N2
5-=1
a(1+T)p
B
V Vu L1
Σ
Vora
Σ - am.d
N2
ND
j=1
a(1 ()
8
Σ
(cr. a.))
vo ND
Σ
(pr.d ab
N2
d=1
38

---

Published as a conference paper at ICLR 2026
N
Se, L/
(Pis - Fi
ND
1=1
and
Vb L2
2 (pi, - Di
ND
Similarly
V L a(1 + 1
(Cni,ny
an,,nzy (ons))nns,n, Unick Dny.k
M
iJ=1
M
Umm T. (M) a(1 + p)
(Cmmong Om Fy. Amm.m P.UUng.k
M
j=l
D
Drom Lig
(M)
(Pamed I Fn
MD
d=1
ax1 +
M
Unmi L
(M)
Σ
(Com.ny ar qumm Th k
M
V Unm
(M)
B
(Pam.d Inm
MD
d=1
(M)
fe.e
Liz
MD
(prid In, un.
and
ba.d
I (M)
B
Σ
M
(pogd Uag
MD
The following Lemma provides an error bound between the sum of 2D array of numbers and the sum of random points from the 2D array. We study the setting where one randomly (and independently) samples only points 1D axis, and the 2D random samples consist of all pairs of these samples. This results in dependent 2D samples, but still, one can prove Monte Carlo-type error bound in this situation. The Lemma similar to Lemma E.3. Finkelshtein et al. (2024a), generalized to non-symmetric matrices.
Lemma H.5. Let (im) J be uniform i.idd in [N]. Let A E NxN with 0z. E [-1, Then, for every 0 < p < 1, in probability more than 1 p
N
N
M
M
2 log(1/p) + 2 log((NN + log(22
N
jj,
M
aim.ii
$ 22
M
j=ln=1
ML
1=1
Proof. Let p 1. For each fixed n E [N], consider the independent random variables
Yn = 0i no with
N
B(Y
Ojn
and -1 - Y,n < Similarly define the independent random variables WR = an with
E(W
an.z
39

---

Published as a conference paper at ICLR 2026
By Hoeffding's Inequality, for h (oo21//00++))
we have
M
M
jnn
Σ
almm
I k
N
M
1=1
m==
and
M
On.
S k
N
M
/=1
m=1
in the event Ex and En of probability more than 1 - p/2N.. Intersecting the events (Ew Jn=1 and (er J. J==1, we get Vn E [N]
M
jn
M
Σ
S k
1=1
m==
and
On
S k
N
M
in the event & = EnE On &W with probability at least 1 p. The rows and columns of A are independent, meaning the probability of their intersection least p and by the triangle inequality, we also have in the event 3
M
N
M
M
asd
S k
NM
M
[=1
m=1
and
N
N
N
M
N
ajn
NM
Ob S k.
1=
R=
m=1
Hence, by the triangle inequality,
N
M
N
Oj.
M
ΣV
Σ
Oim
S
2k.
1=1 m=1
We now derive bounds on the approximation errors for the gradients of L. Note that the gradients of the SGD loss with respect to each element of the IB IGG are
(M)
2 Unm.k
(M)
Unmmk & Liz
(M)
Unm
V Vom
I (M) = 22V Umm.
(M) +
Pemm L
(M)
V ((M) N2 41
(M)
be. (M)) V bz. L2
(M)
Vun (MM) fu.m I (M)
We use Lemmas H. and H.5
These results are applicable in our setting because all entries of the relevant matrices and vectors, A, X, C, P. U. V. r. F, and B are bounded in [-1,1].
40

---

Published as a conference paper at ICLR 2026
Specifically, for any 0 P1 1, for every & [K] there is event As of probability at least 1 P1 such that
V VigL(m)) < 4a(1+ +T
2log(1/pi)
log (N (2N) 2
Moreover, for every & [K] and I [D], and every at least 1 - P2 such that
P2 < 1 there is an event Ck.y of probability
(an) S
43
2 llg((1/p)) + 22)
J
fkmm
D
M
Similarly, for every 0 < Ps there is an event km.m of probability at least Ps such that
L V bu.n L (MM)
4,
2 log(11/p0) (1p3) + (o)(2)
D
M
For the approximation analysis of V unn.. L and V Ver... L, note that the index is random, so we derive a uniform convergence analysis for all possible values of ny. For that, for every n E [N] and [K], define the vectors
V Un. L (M) a(1 + D)
Σ
(Cn.ny On,,y Jqn.ny F
M
D
V un
In2 (M)
"(pnt - InaaJskd.
MD
d=1
and
a(1 + r)
M
(M)
Σ
(Cnin
an,yg T g
Un.k
M
j=l
D
[ (M)
Σ
(Pn,d
In.d) Fn.d)baad-
MD
d=1
Note that V un (M) and V Ve,, LMM are not gradients of (M) (since if n is not sample from {n+}
the gradient must be zero), but are denoted with for their structural similarity V Vanga L (M) and
V Vnnm. (MM, However, we get for every m E [M]
Bum & Tog
L
(M)
Wmm &
and
Pram Loz
(M)
Vrre Lig
Hence, for every
[M], we have
V Bn,k
(MM) = N2 Un.
L (M)
and
(M) 22V vn.k (M)
Let 0 P4 1. By Lemma such that for every n E [N]
H.3 for every i: E [K] there is event Ub of probability least P4
M V un.
I(M)
a(1 a(1+D)p
2log(1/pa) + 2 2og N) + log(2)
V Un La
N
N
M
Similarly, for < P5 that for every [N]
< for every t [K] there is an event VA of probability at least 1 Ps such
V Un.
Tog
M
V
(M))
S
a(1 + DDp
2 log l/ps) + 2 log (N) + log(2)
N
Un.
N
M
41

---

Published as a conference paper at ICLR 2026
This means that in the event UR for every [M] we have
2 2log(1/p4) + (l) + 2 (2)
(M)) - a(1 (a(1+D)uN
N
M
and in the event Vks for every m E [M]] we have
M V
2 2og /ps) + (N) - -222o 2log(2)
L
((M)
aa(1 + +T)NN
N
M
Lastly, given 0 < < 1, choosing P1 P4 = p/5K and P2 Ps P/5KD and intersecting
all events for coordinates gives in the event of probability at least
2 llog(1/p) + (N) + 2 (og(K) + 2 (10
V. L Vea LiM) I 4a(1 + r)uN2
M
Sh.m L
fkm ((M)
28
D V
2 2log(1/p) - 2 log K) log (
M
Vbn.m Vok.on L (an)
23
2log(1/p) + +2log(K) (K)
+2olog ()) 210g(10)
- D
V
M
2log(1/p) + log (N) + (l)((K)))))))) + 2l0
V Oram
L
V
(M)
I a(1 + V
N Unm
M
and
M
2 2log(1/p) + (No(NN) 20g (K) 2 log(10)
L
[(dr)
sa(1 +
N
M
thus proving Theorem
H.4
H.5 COMPARISON OF NODE SAMPLING AND DIODE SAMPLING
Propositions H.I and H.4 both provide a probabilistic bound on the difference between the gradients calculated using subgraph SGD and the standard loss (8) using the full graph. Despite this similarity, these approces differ in their sampling schemes and computational tradeoffs.
For Theorem H.4 unlike Theorem H.1 only subset of entries from U and V are involved in the loss computation per step. This introduces a time-memory tradeoff: since only subset of U and V updated in each step, the number of iterations required grows by a factor of N/M in expectation, and the memory consumption reduces by M/N, where M denotes the number of sampled nodes. This mild growth in runtime is acceptable, the number of iterations only grows by a linear scale, while each iteration becomes faster to complete due to the reduced size of the graph.
For Theorem H.I we sample the diodes of the graph directly. Therefore potentially all nodes of the graph are involved in the calculation of the loss. Using this method, the time and memory complexity of calculating the loss becomes (M,,), where M the number of sampled edges.
Notably, the bounds in Theorem H.I are independent of the graph size, while the bounds in Theo- rem H..4 improve as the graph becomes more dense. However, practice, we see that both diode sampling SGD and node sampling SGD provide good IBG approximations that work well for IBG-NN.
I KNOWLEDGE GRAPHS
I.1 BASIC DEFINITIONS
Knowledge graph signals. We consider knowledge graphs G = (N,ER)) R), where N, and R represent the set of N nodes, the set of E typed edges, where E C R Xx N, and the set of relations, correspondingly. Note that in this case there is signal (i.e. feature matrix). We represent R Frobenius norm. The weighted the graphs by an adjacency tensor T (1ig.))).)
42

---

Published as a conference paper at ICLR 2026
Frobenius norm of tensor where its two first dimension equal D R N with respect to the weight Q (0, (o) is defined to be |Pllrqq Ligjor Segir Eijr d. Big..-
Cut-norm. The weighted lensor cut norm of D E TR. defined to
NRNNR with weights Q E 00) is
Dlla. Enio Pegir r=1
Σ
max U.V.IM
ΣΣ SEU JEV
dis.r
and the definition for the densifying similarity follows.
I.2 APPROXIMATIONS INTERSECTING BLOCKS
We define an Intersecting Block Graph Embedding (IbgE) with K classes (K-IbgE) low rank knowledge graph C' E X x with an adjacency tensor given respectively by
K
Chi.p =
Σ 1=1
The lu,
where T E RR and Uj. V2 C [N]] We relax the {0, 1}-valued hard source/target community affiliation functions 1,, 17 soft affiliation functions in I to allow differentiability.
Definition 1.1. Let d E N, and let 2 be soft affiliation model. We define [2] C RNNNNR to be the set of all elements of the the form ue 8 m, with u, v E Q and m E R.. We call [2] the soft rank-1 intersecting block graph embedding (IbgE) model corresponding
Z. Given K E N. the subset [Q]x k of R x N.Nx x R of all linear combinations of K elements of [2] is called the soft rank- K IbgE
model corresponding to Z.
In matrix form, an IbgE C' E RRNNNXR in [2) can be represented by a triplet of source community
affiiiation matrix V E RNNK targer community affiliation matrix U E N and community relations matrix M E R that satisfies:
Chp.p= diag V
where p E [R].
1.3 FITTING IBGs TO KNOWLEDGE GRAPHS
Given a knowledge graph = (W. R) with N nodes and R relations and an adjacency tensor T E NxxNXR true triple is defined as (n.P,7) p, r), where 7) E N and [R]. We define the following soft rank-K intersecting block score function, based on the weighted Frobenius distance:
d(n. [| un diag(r., u FQQr
where the weight matrix Qr is
Qr Qur: (1 eFE max T. T.i.pr
EE(R)
8(h,r; 1) 1 (h, () a true triplet, otherwise V. T is the source community affiliation of the head entity, U E R the target community affiliation of the tail entity, R., E RR the community relation vector, and cg, 1-(E/N2) with r > 0.
TE/N²
We minimize a margin- based loss function with negative sampling, similar Sun al. 2019
= - log a (7 - d(n, p. T))
log a (d (n/s p/. - 7)
where y is fixed margin, a the sigmoid function, Ç is the number of negative samples and (ol P/g 7() is the i-th negative triplet. An empirical validation of IbgE is provided in Section M.1.2
43

---

Published as a conference paper at ICLR 2026
J COMPARISON OF IBGs TO ICGS
In this section we highlight the key advancements and distinctions between our method and its predecessor (Finkelshtein al. 2024a).
Approximation of directed graphs. Graph directionality is crucial for accurately modeling real- world systems where relationships between entities are inherently asymmetric. Many applications rely on directed graphs to capture the flow of information, influence, or dependencies, and ignoring directionality can lead to the loss of critical structural information. One domain which benefits from directionality is spatiotemporal graphs graphs where the topology is constant over time but the signal varies. For example, in traffic networks Li et al. (2018), where directionality represents the movement of vehicles along roads, traffic congestion in one direction does not necessarily imply congestion in the opposite direction. Thus, ignoring directionality can lead to inaccurate predictions. Another domain is citation networks, where nodes represent academic papers, and directed edges represent citations from one paper to another. The concrete task of prediction of the publication year highly depedant the direction of each edge due the causal nature of the relation between two papers (Rossi et al. 2024). Many more additional domains benefit from directionality, some of which are Email Networks, Knowledge Graphs and Social Networks (Yujie al. 2023 Changping et al. 2020).
An ICG takes on the form
C
P
Where Q is the community affiliation matrix, and F is the community feature matrix. Here, Q is used as both the source and the target affiliation matrix, making the ICG symmetric, undirected graph. The community affiliation matrix Q also acts mapping from the community space the node space, converting the community feature matrix F' to node features.
An IBG takes the form
C == P-UFVV
P-UF+VB
IBG generalizes the ICG by using different affiliation matrix for source nodes V, and target nodes U, enabling approximation of directed graphs. The use of source and target community affiliation matrices naturally leads the use of two community feature matrices. The source community feature matrix, B, and the target community feature matrix, F. Over undirected graphs, the IBG representation converges to the ICG representation.
In our analysis of IBGs, we adopt the simplifying assumption that the approximated graph is unweighted, whereas ICG assumes weighted approximated graph. This assumption is introduced to provide a clearer derivation of our theoretical guarantees; however, it can be relaxed using the same line of derivation with straightforward modifications to account for edge weights,
Densifying the adjacency matrix. The major caveat of ICG-NNs is their limited applicability to sparse graphs. Both their theoretical guarantees and approximation capabilities weaken as sparsity increases, with the approximation error of ICGs being (NN((K)) 1/2). This issue stems from the imbalance between the number of edges and non-edges in sparse graphs. As graphs grow sparser, non-edges dominate, and since standard metrics assign equal weight to edges and non-edges, the approximation shifts from capturing the relational information that we aim to capture to capturing the absence of relations. To address this limitation, we introduce the densifying cut similarity, a novel similarity measure that explicitly accounts for the structural imbalance in sparse graphs. This similarity measure enables IBG-NNs to efficiently learn a densified representation of sparse graphs, achieving an approximation error (K for both sparse and dense graphs while preserving the relational information. We emphasize that, unlike ICGs, whose approximation quality is measured with respect to the cut norm, IBGs are evaluated based on the densifying cut similarity.
Architecture and empirical performance. At first glance, ICG-NNs and IBG-NNs may appear conceptually similar, as both follow a two-step process: first estimating the graph approximation, followed by processing through neural network architecture. Both also support subgraph stochastic gradient descent (SGD) method. However, the fine- mme-grained details their implementations differ significantly.
In the graph approximation stage, IBG-NNs extend the capabilities of ICG-NNs in two ways. They can approximate directed graphs, and more importantly they minimize weighted Frobenius
44

---

Published as a conference paper at ICLR 2026
norm, where edges and non-edges assigned different weights. This contrasts with ICG-NNs, which minimize the standard Frobenius norm. This critical difference enables IBG-NNs to handle sparse graphs more effectively, as demonstrated in Section M.3 In the neural network stage, IBG- NNs offer greater architectural flexibility. While ICG-NNs operate on a single community signal, IBG-NNs incorporate two community signals (source and target) when mapping back to the node space. Although we simplify the architecture by using a basic addition operation, more sophisticated manipulations could be employed. These architectural and methodological advancements result in IBG-NNs' empirical superiority across various domains. Specifically, IBG-NNs outperform ICG- NNs in node classification (see Section 6.2). spatiotemporal property prediction (see Section |MI.I] subgraph SGD on large graphs (see Sections 6.3 and M.1.3). and efficiency in the number of communities used (see Section M.2.TP.. This broad dominance underscores the effectiveness of IBG-NNs in addressing the limitations of ICG-NNs while delivering state-of-the-art performance. Lastly, we note that IBG-NNs uses DeepSets within each layer. We include this component because it improves performance in practice. For faimess in our experiments, we also evaluated an ICG-NN variant using DeepSets and observed no additional gains.
K COMPLEXITY COMPARISON OF IBG-NN AND MPNNS
Our IBG-NN architecture takes O(D(NK + KD + ND)) operations at each layer. For comparison, simple MPNNs such as GCN and GIN compute messages using only the features of the nodes, with computational complexity ( + N D²). More general message-passing layers which apply an MLP to the concatenated features of the node pairs along each edge have a complexity of O(ED²). Consequently, IBG neural networks are more computationally efficient than MPNNs when K < Dd, where d denotes the average node degree, and more efficient than simplified MPNNs like GCN when K < d.
L ADDITIONAL IMPLEMENTATION DETAILS ON IBG-NN
Let us recall the update equation of an IBG-NN for layers 1865-1
H (++1) (0f ( + + (VB()))
((11) (0i H + 0 (UF
And finally for layer L:
(L)) = (L)
In each layer, the learned functions Of and θ; are applied to the previous node representations !!!) (8) and H!!) seperately. while θ; and O₂ are applied to the post-analysis source community features V (f) and the post-analysis target community features ( respectively. To simplify, we restrict the aforementioned architecture of the learned function to linear layers and pooling operation (e.g. DeepSets (Manzil et al. 2017), interleaving with ReLU activation function. example of an IBG-NN linear layer with mean pooling is:
θ (
H (
1 N
II I W
with ( ( E DRD x being learnable weight matrices.
M ADDITIONAL EXPERIMENTS
M. ANALYSIS ON VARYING DOMAINS
M.1.1 SPATIO-TEMPORAL GRAPHS
Setup. evaluatee IBG-NN on the real world traffic-network datasets METR- and PEMS-BA BAY
al. 2018). We report the baselines DCRNN (Li al. 2018), GraphWaveNet (Wu et al. 2019)
45

---

Published as a conference paper at ICLR 2026
Table 3: Results on temporal graphs. Top three models are colored by First, Second, Third.
Model
METR-LA
PEMS-BAY
# nodes
207
325
# edges
1515
2369
Avg. degree
7.32
7.29
Metrics
MAE
MAE
DCRNN
3.22 + 0.01
1.64 + 0.00
Graph WaveNet
3.05 0.03
1.56 0.01
AGCRN
3.16
+.00
T&S-IMP
1.70 0.00
TTS-IMP
+.04
1.72
T&S-AMP
+
+
TTS-AMP
3.00
1.66 0.00
ICG-NN
6.12 0.01
1.56 + 0.00
IBG-NN
3.10 0.01
1.55 + 0.00
Table 4: Comparison with KG completion methods. Top three models colored by First, Second,
Third.
Method
Model
Kinship Hit@1
UMLS
MRR
@it 10
MRR
Hit@
Hit 10
TransE
0.31
0.9
84.1
0.69
52.3
89.7
DistMult
0.35
18.9
75.5
0.39
25.6
66.9
KGE
ComplEx
0.42
24.2
81.2
0.41
27.3
70.0
RotatE
0.65
50.4
93.2
0.74
63.6
93.9
lbgE
0.69
55.0
95.3
0.82
71.5
96.3
Neural-LP
0.30
16.7
59.6
0.48
33.2
77.5
DRUM
0.33
18.2
67.5
0.55
35.8
85.4
Rule Learning
RNNLogic
0.64
49.5
92.4
0.75
63.0
92.4
RLogic
0.58
43.4
87.2
0.71
56.6
93.2
NCRL
0.64
49.0
92.9
0.78
65.9
95.1
AGCRN (Bai et al. 2020). T&S-IMP, TTS- IMP, T&S-AMP, and TTS-AMP (Cini et al. 2024).
and ICG-NN (Finkelshtein al. 2024a) all taken from Finkelshtein et al. (2024a). We follow the methodology of Cini et al. (2024). segmenting the datasets into windows of time steps, and training the model to predict the subsequent 12 observations. Each window is divided sequentially into train, validation, and test using 70% 10% 220% split. We report mean average error and standard deviation over 5 different seeds. Finally, we use GRU to embed the data before using as input for the IBG-NN model.
Results. Table 3 demonstrates that IBG-NNs suppresses ICG-NNs by a small margin. This slight difference could be attributed the small size of the graph (207 and 325 nodes), where local interactions are likely sufficient for the task, and the ability of IBG-NNs to capture global structure becomes less relevant. This raises questions about the role of directionality in traffic networks, suggesting the need for further investigation. Notably, IBG-NNs show strong performance in another domain, matching the effectiveness of methods specifically designed for spatio-temporal data, such as DCRNN, Graph WaveNet, and AGCRN, despite the small graph size and low edge density.
M.1.2 KNOWLEDGE GRAPHS
Setup. We evaluate IbgE on the the Kinship and UMLS (Kok & Domingos 2007) datasets. We
report the knowledge graph embedding baselines TransE (Bordes al. 2013), DistMult Yaagg et al.
2014). ConvE (Dettmers et al. 2018), ComplEx (Trouillon et al. 2016) and RotatE (Sun et all 2019). We also report the rule learning baselines Neural-LP (Yang et al. 2017) RNNLogic (Qu et al. 2020
RLogic (Cheng et al. 2022) and NCRL (Cheng et al. 2023) to compare with the
models these datasets. Results for all baselines were taken from (Cheng et al. 2023)
46

---

Published as a conference paper at ICLR 2026
Table 5: Comparison of node-sampling subgraph SGD with coarsening methods across varying condensation ratios. Top three models are colored by First, Second, Third.
Flickr 1%
Reddit 0.2%
Condensation ratio
0.5%
100%
0.1%
100%
Coarsening
44.5 + 0.1
44.6 + 0.1
47.2 0.1
42.8 + 0.8
47.4 + 0.9
93.9 + 0.0
Random
44.0 +4.0
14.6022
4.1
58.0 2.2
66.3 + 1.9
93.9 +
Herding
43.9 19.91099
0.6
4.1
62.7 1.0
71.0
93.9
K-Center
43.2
44.1 0.4
4.1
53.0
2.1
93.9 1..9:0000
GCOND
47.1
47.1 0.1
47.2
9..
90.1 0.5
93.9
SFGC
47.0 0.1
4.1
47.2 0.1
90.0 0.3
89.9 0.4
93.9
GC-SNTK
46.8 0.1
46.5 + 0.2
SimGC
45.6 0.4
43.8 + 1.5
47.2 0.1
91.1 + 1.0
92.0 0.3
93.9 + 0.0
ICG-NN
50.1 0.2
50.8 + 0.1
52.7 + 0.1
89.7 + 1.3
90.7 + 1.5
93.6 + 1.2
IBG-NN
50.7 0.1
51.2
53.0 0.1
92.3 1.1
92.3
0.6 94.1 0.5
Results. Table shows that IbgE achieves state of the art results across all datasets, solidifying IBGs potential knowledge graph embedding method. This strong performance is expected, as IbgE is both computationally efficient and expressive, capable of modeling arbitrary head-relation-tail triplets, making particularly well-suited for modeling knowledge graphs.
M.1.3 SUBGRAPH SGD USING NODE SAMPLING
Setup. In Section 6.3
test the diode sampling SGD method proposed in Section H In this section
we test the same experiment using the node sampling SGD) method (see Section H.] We follow the setup deseribed in Section 6.3 for Flickr and Reddit, under condensation ratios M/N, where N is the total number of nodes, and M is the number of sampled nodes. For a condensation ratio of 100%, the competing methods correspond to standard GCN.
Results. Once again, Table shows IBG-NN using node sampling subgraph SGD outperforms all other coarsening and condensation methods, as well as its predecessor, ICG-NN. These results consistent with theoretical guarantees (see Theorems H.T and H.4.. which predict low approximation error. This demonstrates that IBG-NNs are capable of good approximations even while loading small fraction of the graph into memory. Additionally, sampling and diode-sampling methods yield nearly identical empirical performance, although their approximation errors decay different asymptotic rates (see Theorems H.1 and H.4). offering flexibility in choosing the sampling strategy based on practical considerations.
observe that node-
M.2
THE EFFECT OF NUMBER OF COMMUNITIES
M.2.1
PERFORMANCE
Setup. We evaluate IBG-NN and ICG-NN on the non-sparse Squirrel and Chameleon graph (Pei ct al. 2020). We follow the 10 data splits of Pei et al. (2020); Li al. (2022b) for Squirrel and Chamelcon reporting the accuracy and standard deviation.
Results. In Figure IBG-NNs exhibit significantly improved performance compared to ICG-NNs. For a small number of communities (10) on Squirrel, IBG-NNs achieve 66% accuracy, whereas ICG-NNs achieve only 45%, further highlighting the superiority of IBG-NNs, allowing to reach competitive performance while being efficient. The performance gap persists across both datasets, with IBG-NNG continuing to improve the number of communities increases, whereas ICG-NNs appear to plateau. This trend can be attributed to IBG-NNs ability to capture directionality in the graph, allowing them model increasingly fine-grained asymmetric structures that ICG-NNs cannot represent.
47

---

0.600 Published as a conference paper at ICLR 2026
Squirrel
IBG-MN
IBG-MN
ICG NN
ICG NN
Number of communities
Number of communities
Figure 3: Accuracy IBG-NNs and ICG-NNs on the Squirrel (left) and Chameleon (right) datasets function of the number of communities.
M.2.2 APPROXIMATION QUALITY
Setup. We evaluate the effect of the number of communities K the densifying cut similarity of the IBG approximation on the Chameleon and Squirrel datasets. compare the weighted Frobenius error to the densifying cut similarity for number of communities ranging from 10 to 250.
Results. As shown in Figure 4 both the densifying cut similarity and the weighted Frobenius error of IBG decrease as the number of communities increases. This stands in line with our theory, and demonstrated the bound in Equation (7 also in fact holds in practice.
Squirrel
Chameleon
Relative Cut Norm
Belative Cut Narm
0.25
0.06
0.00
0.04
0.35
100
20. 200
700
0.00
0.002
0:250
D375
DA10
0.73
020
0.25
0.30
2.35
0.45
0.50
0:55
0.50
Relative Frobenius Norm
Relative Frobenius Norm
Figure Densifying cut similarity as a function of the weighted Frobenius norm on the Squirrel (left) and Chameleon (right) datasets. The number of communities is specified above every point.
M.3 THE IMPORTANCE OF DENSIFYING
M.3.1
DENSIFICATION FOR SPARSE GRAPHS
Setup. We evaluate the effect of proposed densifying lemma by assessing the performance of IBG-NN as a function L, a parameter that controls the weight assigned to non-edges relative to edges the IBG approximation. We explore I' values ranging from where weight assigned only to existing edges, to 1-(E/N2) where a uniform weight of is given to each entry in the adjacency matrix, Our experiments are conducted on the large node classification graph Arxiv-Year (Lim et al. 202T) due its low density (average degree 6.89).
E/N²
Results. Figure presents that the perfromance of densified IBG-NNs with r 1-(E/N²) to that IBG-NNs learned with standard unweighted loss, matching expectations. More importantly, Figure shows that densified IBG-NNs consistently outperform GBG-NNs learned with standard unweighted loss, across all the densification scales, validating that the theoretical improvements also translate into significant practical benefits.
EyN= equals
48

---

Published as a conference paper at ICLR 2026
Table 6: Comparison of node-sampling subgraph SGD with and without densification.
Flickr
Reddit 0.2%
Condensation ratio
0.5%
1%
100%
0.1%
100%
ICG-NN
50.1 1 0.2
50.8 0.1
$2.7 1 0.1
89.7 1: 1.3
90.7 1.5
93.6 1: 1.2
IBG-NN (no densification)
49.6 0.1
50.1
0.2
$2.1 1
89.3
1.1
90.9
93.4
IBG-NN
50.7.1 0.1
51.2 0.2
53.0 1 0.1
92.3 + 1.1
92.3
0.6
94.1 1 0.5
Anxiv-Year
Dersified
Unitorm Weight IBG
60
55
Accuracy
40
weight
10a
10a
102
10
10
Densification Parameter
Figure 5: IBG-NN accuracy the sparse dataset Aear function of T. The dotted line is IBG-NN accuracy when using standard uniformly weighted loss for the IBG approximation, The rightmost point is the value of I which results uniform cut norm under the densifying loss.
M.3.2 DENSIFICATION FOR LARGE GRAPHS
Setup. We repeat the node-sampling subgraph SGD experiment from Section M.1.3 We compare IBG-NN with and without densification ICG-NN, evaluating the importance densification for IBG-NN on the large, undirected graphs Flickr and Reddit.
Results. Table 6 reveals that densification significantly impacts the performance of IBG-NN for large graphs. Here, IBG-NN without densification achieves results comparable to ICG-NN. When adding densification, IBG-NN significantly outperforms ICG-NN, further demonstrating the importance of our contribution.
M.3.3 EFFECT OF DENSIFICATION ON APPROXIMATION QUALITY
Setup. We study the approximation error of ICG and IBG on their target metries, cut metric and densifying cut similarity, when approximating Erdös-Rényí graphs with 1000 nodes on different range of edge probabilities. We set the densification parameter T = 1/2p when approximating ER(1000. p).
Results. Figure Figure Gclearly demonstrates that the approximation quality of IBG remains consistent across different sparsity levels, while ICG's deteriorates as the graphs grow sparser. This greatly supports claims that IBGs learn densified version of the original graph while still sharing the same structure with the original graph.
M.4 EFFICIENCY ANALYSIS
M.4.1 MEMORY ANALYSIS
Setup. We compare the IBG approximation and IBG-NN forward pass memory complexity to that of GCN. We Erdōs-Red Rényi ER(n,p 0.5) graphs with up 7k nodes and sample node features uniformly from U0, 1] with dimension 128. We test IBG-NN and GCN with 3 layers, and hidden and output dimensions of 128.
49

---

Published as a conference paper at ICLR 2026
Er(1000, p)
IBG approximation
ICG approximation
Relative cut similarity
0.2
0.0
0.1
0.2
0.3
0.4
0.5
0.6
Edge probability
Figure 6: Cut norm and densifying cut similarity of ICG and IBG approximations on ER(10000,))
for different values p.
Results. Figure 7 clearly shows IBG's memory complexity scales linearly with GCN, while IBG- NN's memory complexity has square root relationship with that of GCN. This result stands strongly line with the results in Figure 2] as both the time and memory complexity IBG approximation and IBG-NNs are (EE) and (NN) respectively.
FR(n, p(n) = 0.5)
ER(n.p(n) 0.5)
4000
0.3587x
-84.7502
IBG approximation pass
3000
K 100
3.0531x
77.5039
IRGINN pass [MB]
60
R' 0.9989
50
2000
40
K 10
11.9143V 5.8865
1000
30
-0.8850
K 100
20
2.0316VX
5.7051
0.9858
200
400
600
800
1000
1200
1400
200
400
600
800
1000
1200
1400
GCN [MB]
[MB]
Figure Memory complexity of K-IBG (left) and K-IBG-NN (right) as function of GCN forward pass ER(n, 0.5) graphs for K=10, 100.
M.4.2 TIME UNTIL CONVERGENCE OF IBG APPROXIMATION
Setup. We test the time until convergence (in seconds) of the IBG approximation process when using our proposed SVD initialization method (G) vs. when using random initialization. We consider the IBG representation to have converged if the loss in (8) has not improved by 0.5% for over 500 epochs. We perform our comparison on the directed graphs Squirrel, Chameleon, and Tolokers, reporting mean time until convergence and standard deviation over 5 different seeds.
Table 7: Time until convergence in seconds on directed graphs.
Squirrel
Chameleon
Tolokers 11758 519000
nodes edges
5201
2277 36101 15.85
217073
avg. degree
41.71
88.28
random init.
139.63 = 10.58
101.69 6.56
184.54 = 13.94
eigenvector init.
107.20 + 2.73
99.22 7.24
65.89 + 0.39
Results. Table 7 indicates that SVD initialization consistently converges faster than random initial- ization across all datasets. Notably, for Tolokers, using SVD initialization results in nearly 3x faster convergence, highlighting the benefits of the method.
50

---

Published as a conference paper at ICLR 2026
M.5 ADDITIONAL EXPERIMENTS
M.5.1 HYPERPARAMETER SENSITIVITY
Setup. We evaluate the sensitivity of IBG-NN to the number of communities K and the densification parameter I' on three datasets: Squirrel, Chameleon (Pei et al. 2020), and Arxiv- Year (Lim et al. 2021). We train IBGs with varying values of and I, with K E (25, 50, 100, 200, 250, 400) and GE, (0, 0.01, 0.05, 0.1, 0.25, 1}, where fg. implies densification was used. We report test accuracy averaged over the 10 of Pei et al. 2020) splits for Squirrel and Chameleon, and over seeds for Arxiv- Year.
72.3
742
74.0
702
77.4
78.5
45.3
65.4
47.2
67.2
75
76.3
76.8
17.
790
33.4
48.9
42.7
76.1
76.0
771
791
33.4
$4.0
76.8
77.2
76.8
77.8
92.7
45.0
72.8
72.5
75.4
48.6
56.5
dess
dets
120
400
23
100 20
120
482
Figure 8: Accuracy of IBG-NN across different node classification benchmarks under varying values of and eg,r- Top score is marked by red boarder.
Results. Figure 8 shows test accuracy heatmaps for different (K, I') combinations, with red boxes indicating optimal configurations. The results reveal that K = 250 and cÆ, = 0.05 consistently achieve top performance across all three datasets. Moreover, a general trend seems to be that (K, eg,r) points that are further away from (K = 250, eg, 0.05) have worse performance than closer ones, suggesting (K 250, Eg.r 0.05)
promising starting point.
The table also showcases (K = 25, eæ,r 0.01) as a more efficient alternative which uses less communities, while still remaining close in accuracy the top-performing choice.
M.5.2 SVD INITIALIZATION
Setup. We the IBG approximation quality and downstream IBG-NN performance when using random initalization compared to SVD initialization. We report results on the directed node classification benchmarks Squirrel, Chamelon, and Tolokers. evaluate the IBG approximation we report the IBG loss (Equation AUC and standard deviation for Tolokers, and average accuracy and standard deviation for Squirrel and Chameleon, following the 10 splits of Platonov al. (2023); ; Pei et al. (2020).
with standard deviation over 5 seeds. We report average ROC
Table 8: Effect of initialization on IBG loss and downstream IBG-NN accuracy.
Squirrel
Chameleon
Tolokers
IBG loss
IBGNN acc.
IBG loss
IBGNN
IBG loss
IBGNN acc.
random init.
0.22 + 0.01
77.36 + 1.62
0.19 + 0.01
79.59
1.02
0.40 0.01
83.41 + 0.87
eigenvector init.
0.23 + 0.01
77.41 + 1.79
0.17 1 0.01
79.65
1.13
0.40 + 0.01
83.40 1 0.75
Results. As seen Table X SVD initialization results in little to no change in IBG approximation quality and IBGNN performance. This further demonstrates the practicality of our initialization, as it offers improved approximation runtime efficiency with no performance drawback.
M.5.3 CONVERGENCE OF IBG APPROXIMATION
Setup. To validate the stability and efficiency of our proposed method, we analyze the progression of the IBG approximation loss throughout the optimization process. We conduct experiments three benchmark datasets: Squirrel, Chameleon, and Arxiv- Year. For each dataset, we track the IBG loss over 5,000 epochs, reporting average loss and standard deviation over different seeds.
51

---

Published as a conference paper at ICLR 2026
IBG Approximation Loss Progression
Squirel
Chameleon
Arxiv-eer
IBG Approdimation LoGs
3.0
0.8
0.0
02
2000 8000 3200
4000 5000
Epoch
Figure 9: IBG approximation loss during IBG approximation process for Squirrel, Chameleon, and Arxiv- Year.
Results. As seen in Figure across all datasets, the loss converges rapidly in the early stages of training, with minimal improvement observed after 1000 epochs. While the loss continues to decrease slowly with additional training, observe that extending training beyond 10000 epochs rarely leads to additional improvement downstream IBGNN performance.
M.5.4 TOPOLOGICAL ANALYSIS
Setup. To evaluate how graph structure may affect IBG approximation quality and IBG-NN performance, we analyze several graph properties (Homophily level, Density, Cheeger constant, and Spectral gap) across six datasets, and examine their relationship the IBG approximation quality and downstream IBG-NN performance.
Table 9: IBG approximation error and downstream performance over.
Homophilic
Heterophilic
Metric
Citesecr-full
Cora-ML
Ogbn-Arxiv
Chameleon
Squirrel
Arxiv-year
Homophily
0.949
0.792
0.655
0,235
0.223
0.221
Density
0.0006
0,0009
0.0001
0.0121
0.0147
0.0001
Cheeger Const.
0
0.0004
0.0032
0.0218
0.0004
Spectral Gap
1.7
58.9
25.1
194.9
58.9
IBG Approx. Error
0.56
0.75
0.89
0.17
0.23
0.91
IBG-NN Performance f
92.40
84.20
65.30
80.15
77.63
60.14
Table 9 reveals that, despite the differences across the homophily level, density, Cheeger constant, and spectral gap, IBG-NN performance shows no clear correlation with these properties. While IBG approximation error is lower for denser graphs such Chameleon and Squirrel, this does not directly translate to superior IBG-NN performance. These findings may suggest that graph structure alone does not determine IBG-NN performance, factors like node feature quality and lask-specific characteristics also play crucial roles.
Results.
N CHOICE OF DATASETS
We present IBG-NNs, a method best suited for large graphs, capable of effectively approximating directional graphs. Consequently, primary experiments in Section 6..3 follow the standard graph coarsening and condensation benchmarks Reddit (Hamilton al.) 2017a). Flickr (Zeng et al. 2019), Ogbn-Arxiv and products (Hu al. 2020), where IBG-NNs demonstrates oftt--of-the-art
52

---

Published as a conference paper at ICLR 2026
performance. We note that the sirge-graph benchmarks commonly adopted large-scale directed graph datasets.
undirected, there are
Additionally, IBG-NNs used for handling directed graphs. To evaluate its performance in this domain, we conduct experiments on standard directed graph datasets Squirrel, Chamelcon (Pei et al. 2020), and Tolokers (Platonov al. 2023), where also achieves sate-of-theear results. Finally, graph approximation method proves particularly efficient for spatio-temporal datasets, where fixed topology supports time-varying signals. We validate this by experimenting with IBG-NNs the METR-LA and PEMS-BAY Li et al. (2018) datasets, where it matches the effectiveness of methods that are specifically designed for spatio-temporal data.
O DATASET STATISTICS
The dataset statistics of the real-world directed graphs, spatio-temporal, graph coarsening and knowledge graph benchmarks used presented below in Tables I0 13
Table 10: Non-sparse node classification dataset statistics.
Squirrel
Chameleon
Tolokers
# nodes (N)
5,201
2,277
11,758
edges (E)
217,073
36,101
519,000
Avg. degree (
41.71
15.85
88.28
# node features
2089
2325
10
classes
5
2
Metrics
Accuracy
Accuracy
ROC AUC
Table 11: Spatio-temporal datasct statistics.
METR-LA PEMS-BAY
# nodes (N) # edges (E)
207
325
1,515
2,369
Avg. degree (
7.32
7.29
# node features Metrics
34272
52128
MAE
MAE
Table 12: Graph coarsening dataset statistics.
Flickr
Reddit
Ogbn-Arxiv
Products
# nodes (N)
89,250
232,965
169,343
2,449,028 029
# edges (E)
899,756
114,615,892
1,166,243
61,859,140
Avg. degree (E/N)
10.08
491.99
6.89
25.26
# node features
500
602
128
100
# classes
40
Metrics
Accuracy
Micro-F1
Accuracy
Accuracy
Table 13: Knowledge graph completion dataset statistics.
Kinship
UMLS
entities
104
135
# relations
25
46
# training triples
8,544
5,216
# validation triples
1,068
652
# testing triples
1,074
661
Avg. train. degree
82.15
38.64
P HYPERPARAMETERS
All experiments conducted on single NVIDIA L40 GPU, using the Adam optimizer.
53

---

Published as a conference paper at ICLR 2026
In Tables 14 to report the hyper-parameters used in real-world directed graphs, spatio- temporal, graph coarsening and knowledge graph completion benchmarks.
For our spatio-temporal experiments, utilize the time of the day and the one-hot encoding of the day of the week as additional features, following Cini et al. (2024). Additionaly, for spatio-temporal graphs usually ignore the signal when fitting the IBG to the graph, but can also concatenate
random training signals and reduce their dimension to obtain one signal with low dimension D to be used the target signal for the IBG optimization.
Table 14: Non-sparse node classification hyperparameters.
Squirrel
Chameleon Tolokers
# communities Encoded dim
250
250
50
128
128
3/a
1
I'
20
Approx.
0.03
0.03
0.03
Approx. epochs
10000
10000
10000
# layers Hidden dim
7
6
128
128
128
Dropout
0.2
0.2
0.2
Residual connection
V
Jumping knowledge
Cat
Cat
Max
Normalization
True
True
True
Fit Ir Fit epochs
0.003
0.003
0.003
1500
1500
1500
Table 15: Spatio-temporal node regression hyperparameters.
METR-LA PEMS-BAY
# communities Encoded dim 8/a
50
100
0
0
I'
0
0
Approx. Ir Approx. epochs
0.01, 0.05
0.01, 0.05
10000
10000
# layers Hidden dim
6
6
128
128
Dropout
0.0
0.0
Residual connection
V
V
Jumping knowledge
Max
Cat
Normalization
True
False
Fit Ir
0.003
0.001
Fit epochs
300
300
54

---

Published as a conference paper at ICLR 2026
Table 16: Graph coarsening node classification hyperparameters. On Flickr and Reddit use 750 communities for condensation ratio of 100%, and 50 communities for the other settings.
Reddit
Flickr
Ogbn-Arxiv
Products
# communities Encoded dim
50, 750
50, 750
50
50
3/a
0
0
5
5
5
Approx. Ir
0.05
0.05
0.05
0.05
Approx. epochs
1000
1000
2500
2500
# layers
4
3
4
Hidden dim
128
256
256
128
Dropout
0
0
Residual connection
V
Jumping knowledge
Max
Cat
Max
Max
Normalization
True
True
True
True
Fit Ir
0.003
0.003
0.003
0.003, 0.005
Fit epochs
1500
1500
1500
1500
Table 17: Knowledge graph completion hyperparameters.
Kinship
UMLS
# communities
20
15
Encoded dim
24
48
Approx. Ir
0.05
0.003
Approx. epochs
250
750
# negative samples
64
128
55


Reviews:
[{"review_id": "QVE5Lye5tM", "reviewer": "Reviewer_tVWW", "summary": "This paper proposes a novel low-rank approximation method for general directed graphs, called Intersecting Block Graph (IBG), designed for efficient graph signal processing. IBG is a non-trivial extension of the Intersecting Community Graph (ICG), overcoming key limitations such as poor performance on sparse graphs and the restriction to undirected graphs. By introducing a densifying cut similarity and an efficient semi-constructive weak regularity lemma, IBG achieves accurate approximations with rank independent of graph size or sparsity. The paper also presents an efficient gradient-based algorithm for fitting IBGs to large directed graphs. Building on this representation, the proposed IBG-NN architecture delivers state-of-the-art results across multiple domains, including node classification, spatio-temporal graph analysis, and knowledge graph completion, while significantly reducing computational complexity.", "questions": "How sensitive is the performance to the choice of hyperparameters such as $\\Gamma$ and $K$ in practice? Any guidelines for setting these?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall the work is well motivated and demonstrates strong empirical results. The paper introduces a densifying weak regularity lemma for directed graphs, which improves upon prior formulations and is supported by sound proofs. It demonstrates robustness to sparsity through the use of a weighted Frobenius norm and densifying cut similarity, enabling accurate approximation of sparse graphs as validated by experimental results. Empirically, the proposed IBG-NN architecture achieves state-of-the-art performance across diverse tasks, including node classification, spatio-temporal graph analysis, and knowledge graph completion. Furthermore, the work emphasizes reproducibility by providing a public codebase and detailed hyperparameter settings, ensuring that the results can be reliably replicated.", "weaknesses": "Performance seems depend on the hyperparameters such as $\\Gamma$ and $K$, but tuning guidelines are minimal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "9gLcOThQPi", "reviewer": "Reviewer_zVnQ", "summary": "This paper presents a method for approximating a large graph that makes the GNN computation on the approximated graph linear with respect to the number of edges, representing a significant improvement over existing graph reduction methods. The approach compresses the original graph by extracting several communities that may overlap and have internal connections represented as bipartite graphs, referred to as blocks or directed communities. Specifically, it employs an extended version of WRL to solve the approximation with strong practical performance, although the theoretical guarantee may be limited.", "questions": "1. Typo of the number of the edges in line 38 (not it’s smaller than the number of nodes)?\n2. Elaborate on `special interpretation' in line 72.\n3. The intuition of the weight cut norm can be introduced in line 83 to improve the readability.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The large computation required by MPNN or GNN on large graphs is indeed a problem, which hinders our understanding and analysis of large social networks, user item interactions in large recommendation networks, and similar systems.\n2. The proposed method is not restricted to undirected graphs, unlike ICG. The objective function can be efficiently optimized using gradient descent.\n3. The number of communities in the method is independent of any property of the graph, including the number of nodes and the sparsity level.", "weaknesses": "1. The semi constructive nature of the optimization is a problem. Then what guarantees do you have, or at least under what conditions of the graph structure, for instance, would you have confidence in the optimization results with guarantees? This would be essential, even though you claim in my comment strength 3) \n2. Explicitly encouraging density is counterintuitive to me, since it is usually natural to think that in real world graphs, many edges are consequences of other edges. This makes the sparsification of graphs under certain principles appealing. Could you elaborate on your thoughts about this?\n3. Does the proposed IBC happen to align with some graph assumptions in real world data? Since in various real world tasks, IBC performs well with its ability to compress the graph by extracting community wise bipartite graphs. Beyond the numerical improvements, it would be very interesting and necessary to include some real world examples in those datasets explaining why condensing the graph in this way would improve performance even beyond the original one, for both heterophilic (I think the performance is very good) and homophilic graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "hMCE2wwZ2o", "reviewer": "Reviewer_jEYc", "summary": "This paper proposes **Intersecting Block Graphs (IBGs),** low-rank directional graph representation allowing the efficient learning on large and even sparse graphs, by squeezing the adjacency matrix into a smaller matrix regarding communities. Additionally, the authors introduce a densifying cut similarity metric and prove a corresponding weak regularity lemma for their claim. The method is validated with various benchmarks with complexity analysis.", "questions": "1. SVD initialization (section M)\n\nWhile the SBD initialization was used against random initialization for faster convergence, I don’t see any performance comparison. Does the performance of two initialization eventually end up in the same?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Theorems and lemmas introduced (quality, clarity)\n\nSection 4 introduces the semi-constructive weak regularity lemma and its proof, developed upon prior work.\n\n2. Competitive performance (significance)\n\nFor node classification, the spatio-temporal graph, and knowledge graph, show competitive performance against the baselines. Additionally, it is relevant for sparse and dense graphs.\n\n3. Efficient architecture (significance)\n\nThe proposed method achieves a time complexity proportional to the number of nodes instead of edges, i.e., the complexity of MPNNs.", "weaknesses": "I do not find any critical weakness\n\nMinor\n\n- figure 1 is not mentioned\n- line 218 - IBG, IGBS are both used", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "wiM7bEpM3t", "reviewer": "Reviewer_Besy", "summary": "The paper works with graph approximations roughly based on the stochastic block model, i.e. approximating the adjacency matrix of the original graph as the sum of multiple blocks, i.e. bipartite subgraphs where all source nodes are connected to all target nodes.\nIn contrast to previous work where the number of blocks needed to achieve a given approximation quality depends on the sparsity of the graph, the paper guarantees this depending only on the approximation quality itself.\nThey also showed that good enough approximations can practically be found in reasonable time and thus a GNN based on the approximation is able to run in time depending only on the number of nodes (and blocks) instead of linear in the number of edges compared to message passing. \nThe implemented GNN achieves very good performance over a number of tasks on relatively large graphs.", "questions": "see weaknesses", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- a much improved regularity lemma and corresponding metric that greatly improves over the predecessor architecture\n - a fast enough algorithm to compute the graph approximation\n - complemented by a GNN building on the graph approximation achieving SOTA performance on a variety of datasets\n - there is a vast and clean appendix explaining all the details of the paper and sufficient background.\n - The paper is easy to read for a theory paper", "weaknesses": "Overall, the paper is very easy to read (especially for a theory paper). I only have a few smaller remarks:\n\n- It could be more clear whether the representation in terms of blocks for IBG and ICG is actually the same. If there is a discussion about it in the paper, I missed it and glancing over the ICG paper the difference is not immediately clear. (As, following this question is the exact role of $\\textbf{b}$ in the definition of $\\textbf P$, as this seems to be the main modification). The description in the appendix could also include pointers to how exactly the differences show themselves in the definitions.\n- mapping the statement of Thm 4.1 to the claims about the contributions roughly works, but a 2-line explaination below would have been nice as well. But I guess due to space, this won't be possible.\n- in 163 in the definition of the weighted cut: what does the i,j in the normalization factor range over? Is it all of Q or just U,V? (potentially use different indices within and outside of the max to make the difference more clear, given that its indeed ranging over all of Q)\n- the workings of the IBG NN compared to a MPGNN is not clear (344ff). Is it doing something else than running a plain directed GNN on the approximated graph, taking into account the low-rank decomposition to make it fast? Or does the model behave differently? This is also relevant for the context in which the \"simple and efficient operations\" in 411 are to be understood.\n\nMinor:  \n- would it be possible to add references to the sources of each line in table 1? This would also make it clear which of the computations are new. (I know that it is described in the text later on, but simple hyperlinks could help as well and in the text)\n\nTypos:  \n248: soft indicator model -> soft affilitation model?  \n444: kipf and welling -> citep  \n461: performance", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)