Learning on Large Graphs using Intersecting Communities
Authors: Ben Finkelshtein
Ismail Ilkan Ceylan
Michael M. Bronstein
Ron Levie
Venue: NeurIPS 2024 poster (2024)
Keywords: graph representation learning
graph neural networks
regularity lemma
intersecting communities
graphon
scalability
Primary area: graph_neural_networks
TL;DR: We show how to approximate graphs by intersecting communities, which allows an efficient learning algorithm on large non-sparse graphs.

Abstract: Message Passing Neural Networks (MPNNs) are a staple of graph machine learning. MPNNs iteratively update each node’s representation in an input graph by aggregating messages from the node’s neighbors, which necessitates a memory complexity of the order of the __number of graph edges__. This complexity might quickly become  prohibitive for large graphs provided they are not very sparse.  In this paper, we propose a novel approach to alleviate this problem by  approximating the input graph as an  intersecting community graph (ICG) -- a combination of intersecting cliques. The key insight is that the number of communities required to approximate a graph  __does not depend on the graph size__. We develop a new constructive version of the Weak Graph Regularity Lemma to efficiently construct an approximating ICG for any input graph. We then devise an efficient graph learning algorithm operating directly on ICG in linear memory and time with respect to the __number of nodes__ (rather than edges).  This offers a new and fundamentally different pipeline for learning on very large non-sparse graphs, whose applicability is demonstrated empirically on node classification tasks and spatio-temporal data processing.

Learning on Large Graphs using Intersecting Communities
Ben Finkelshtein University of Oxford
ismail Îlkan Ceylan University of Oxford
Michael Bronstein
Ron Levie
University of Oxford / AITHYRA
Technion - Israel Institute of Technology
Abstract
Message Passing Neural Networks (MPNNs) are staple of graph machine learning. MPNNs iteratively update each node's representation in an input graph by aggregat- ing messages from the node's neighbors, which necessitates a memory complexity of the order of the number of graph edges. This complexity might quickly become prohibitive for large graphs provided they are not very sparse. In this paper, we propose a novel approach to alleviate this problem by approximating the input graph as an intersecting community graph (ICG) - combination of intersecting cliques. The key insight is that the number of communities required to approximate graph does not depend on the graph size. We develop a new constructive version of the Weak Graph Regularity Lemma to efficiently construct an approximating ICG for any input graph. We then devise an efficient graph learning algorithm operating directly on ICG in linear memory and time with respect to the number of nodes (rather than edges). This offers a new and fundamentally different pipeline for learning very large non- non-sparse graphs, whose applicability is demonstrated empirically on node classification tasks and spatio-temporal data processing.
1 Introduction
The vast majority of graph neural networks (GNNs) learn representations of graphs based on the message passing paradigm [22], where every node representation is synchronously updated based on an aggregate of messages flowing from its neighbors. This mode of operation hence assumes that the set of all graph edges are loaded in the memory, which leads Specifically, considering a graph with N nodes and E' edges, message- saataaggeppsiinggggg leads to a memory complexity that is linear in the number of edges, which quickly becomes prohibitive for large graphs especially when E > N. This limitation motivated body work with the ultimate goal of making the graph machine learning pipeline amenable to large graphs
memory complexity bottleneck.
24 13
65
In this work, we take a drastically different approach to alleviate this problem and design novel graph machine learning pipeline for learning over large graphs with memory complexity linear in the number of nodes. At the heart of our approach lies a graph approximation result which informally states the following: every undirected graph with node features can be represented by a linear combination of intersecting communities (i.c., cliques) such that the number of communities required to achieve certain approximation error is independent of the graph size for dense graphs. Intuitively, this results allows us to utilize an "approximating graph", which we call intersecting community graph (ICG), for learning over large graphs. Based on this insight radically departing from the we propose a new class of neural networks acting on the ICG and the set of nodes from the original input graph, which leads to algorithm with memory and runtime complexity that is linear in the number nodes.
standard message- -aaggggg-psnngggggg paradigm
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Our analysis breaks the traditional dichotomy of approaches that are appropriate either for small and dense graphs or for large and sparse graphs. To our knowledge, we present the first rigorously motivated approach allowing to efficiently handle graphs that are both large and dense. The main advantage lies in being able to process a very large non-sparse graph without excessive memory and runtime requirements. The computation of ICG requires linear time in the number of edges, but this is an offline pre-computation that needs to be performed once. After constructing the ICG, learning to solve the task on the graph the most computation demanding aspect - is very efficient, since the architecture search and hyper-parameter optimization is linear in the number of nodes.
Context. The focus of our study is graph-signals: undirected graphs with node features, where the underlying graph is given and fixed. This is arguably the most common learning setup for large graphs, including tasks such as semi-superviser
(transductive) node classification. As we allow
varying features, our approach is also suitable for spatiotemporal tasks on graphs, where a single graph is given as a fixed domain on which a dynamic process manifests as time-varying node features. Overall, our approach paves the way for carrying out many important learning tasks on very large and relatively dense graphs such as social networks that typically have 10 10 nodes and average node degree of 102 ~ 10x [19] and do not fit into GPU memory.
Simple graph
Challenges and techniques. There are two fundamental technical challenges to achieve the desired linear complexity, which we discuss and elaborate next.
How to construct the ICG efficiently with formal approximation guarantees? adaptation of the Weak Regularity which proves the existence of an approximating ICG in metric well-known graph similarity meausre Differently from the Weak Regularity Lemma, however, we need to construct an approximating ICG. Directly minimizing the cut metric is numerically unstable and hard to solve We address this in Theorem 3.1 by proving that optimizing the error in Frobenius norm, a much easier optimization target, guarantees small cut metric error. Hence, we can approximate uniformly "granular" adjacency matrices by low-rank ICGs in cut metric. Uniformity here means that the number of communities K of the ICG required for the error tolerance e is k= independently of on any property of the graph, not even its size N This result allows us to design an efficient and numerically stable algorithm. Figure Sigure[ssone shows an adjacency matrix with an inherent intersecting community structure, and our approximated ICG, which captures the statistics of edge densities, ignoring their granularity.
Our answer to this question
Lemma 20 38
Approximating ICG
Figure 1: Top: ad- jacency matrix of simple graph. Bot- tom: approximating community ICG.
How to effectively use ICG for efficient graph learning? We present a signal processing framework and deep neural networks based on the ICG represen-
tation (ICG-NN). As opposed to message- message-passing networks that require O(E) memory and time complexity, ICG-NNs operate in only (NN) complexity. They involve node-wise operations allow processing the small-scale granular behavior of the node features, and community operations that account for the large-scale structure of the graph. Notably, since communities have large supports, ICG-NN can propagate information between far-apart nodes in a single layer.
Contributions. Our contributions can be summarized as follows:
We present novel graph machine learning approach for large and non-sparse graphs which enables O(N) learning algorithm on ICG with one-off O pre-processing cost for constructing ICG. Technically, we prove constructive version of Weak Regularity Lemma in Theorem 3.1 to efficiently obtain ICGs, which could be of independent theoretical interest.
We introduce ICG neural networks as an instance of signal processing framework, which applies neural networks on nodes and on ICG representations.
Empirically, we validate our theoretical findings on semi-supervised node classification and on spatio-temporal graph tasks, illustrating the scalability of our approach, which further supported by competitive performance against strong baseline models.
20 proposed an algorithm for finding the ICG, but it has impractical exponential runtime (see Section 7
Thhe definition of cut metric involves maximization, so minimizing cut metric is unstable min-max.
"Note that the optimal Frobenius error is not uniformly small, since adjacency matrices of simple graphs are {0, 1a-aule typically very granular, so they cannot be approximated well by low-rank R-valued ICG matrices. Nevertheless, if we find an approximate Frobenius minimizer, are guaranteed small cut metric error.

---

2 A primer on graph-signals and the cut-metric
Graph signals. We are interested in undirected (weighted or simple), featured graphs G (N, S). where N denotes the set of nodes, & denotes the set of edges, and S denotes the node feature matrix, also called the signal. We will write N represent the number of nodes and E represent the number of edges. For ease of notation, we will assume that the nodes are indexed by [N] (I.....N}. Using the graph signal processing convention, we represent the graphs in terms of graph-signal G = (A, S)) where A (e E X is the D-channel signal. We assume that the graph is undirected, meaning that A is symmetric. The graph may be unweighted (with at {0, 1}) weighted (with at, [0, 1).. We additionally denote by 8, the n-th row of S, and denote S (s,) By abuse of notation, we also treat a signal as the function S [N] + RD with S(n) = Sn, We suppose that all signals are standardized to have values in [0, 1]. In general, any matrix (or vector) and its entries are denoted by the same letter, and vectors are seen as columns. The i-th row of the matrix A is denoted by Ai.: and the j-th column by A.j- The Frobenius norm of a square matrix
N E RNXN is the adjacency matrix, and S
M E NNN is defined by || 1F
and for a signal S RN by || = V / N En Ej |sn]1 1- The Frobenius norm of a matrix-signal, with weights a, b > 0,
V
[bn.ml? -
is defined be ((M.S)ll == Va VaIME + b|Ss We define the degree of weighted graph as deg A) N2 || In the special case of an unweighted graph get deg (A) E. The pseudoinverse of full rank matrix M RR*K where N > K, is M (M* M)-1MT Cut-metric. The cul metric is a graph similarity, based on the cul norm. We show here the definitions for graphs of the same size; the extension for arbitrary pairs of graphs based on graphons (see Appendix B.2). The definition of matrix cut norm is well-known, and we normalize it by parameter E E N that indicates the characteristic number of edges of the graphs of interest, so cut norm remains within a standard range. The definition of cut norm of signals is taken from 33
Definition 2.1. The matrix cut norm of M E R NNN, normalized by E, is defined to be
| = | |M I,N,E
1
sup
ΣΣ
miji
(1)
E UUVEI
JEV
The signal cut norm 2 E RND is defined to be
1 l = 11 = DN
Σ
sup [C[
Σ 25.
iEW
The matrix-signal cut norm of (M, Z), with weights a > 0 and 3 > O.t. a 3 = 1, is defined to be
[I(M, Z) = [M,, 2) llo,, = a || || + B B O.N
(3)
Given two graphs A, A', their distance in cut metric is the cut norm of their difference, namely
1 | A'l E U.VCIN] NEW
ΣΣ (ois (ois-d(a)--
4
The right-hand-side of (4) interpreted as the difference between the edge densities A and A' on the block on which these densities are the most dissimilar. Hence, cut-metric has probabilistic interpretation. Note that for simple graphs, A- A' is a granular function: it has many jumps between the values - 1. 0 and 1. The fact that the absolute value in 4 is outside the integral. as opposed to being inside like in E norm, means that cut metric has an averaging effect, which mitigates the granularity of A A'. The graph-signal cut metric is similarly defined to be ((A,)) (A'S'')ll
Cut metric in graph machine learning. The cut metric has the following interpretation: two (deterministic) graphs are close to each other in cut metric iff they look like random graphs sampled from the same stochastic block model. The interpretation has precise formulation in view of the Weak Regularity Lemma 20 38 discussed below. This makes the cut metric a natural notion of similarity for graph machine learning, where real-life graphs are noisy, and can describe the same underlying phenomenon even if they have different sizes and topologies. Moreover, [33] showed that
3

---

GNNs with normalized sum aggregation cannot separate graph-signals that are close to each other in cut metric. In fact, cut metric can separate any non-isomorphic graphons [37], so it has sufficient discriminative power to serve as a graph similarity measure in graph machine learning problems. As opposed to past works that used the cut norm to derive theory for existing GNNs, e.g., [46 40 [3], we use cut norm to derive new methods for a class of problems of interest. Namely, we introduce
new theorem about cut norm - the constructive weak regularity lemma (Theorem 3.1 ) and use it to build new algorithms on large non-sparse graphs.
3 Approximation of graphs by intersecting communities
3.1 Intersecting community graphs
Given a graph G with N nodes, for any subset of nodes 4 C [ denote by Du its indicator (i.e., [1( = i E U and zero otherwise). We define an intersecting community graph-signal (ICG) with K classes (K-ICG) as a low rank graph-signal P) with adjacency matrix and signals given respectively by
P)
K C G-Err Lu, Lu
K
P
P= Mu J]
Σ
(5)
where r, & RP, and un C [N]. In order to allow efficient optimization algorithms,, relax the {0. 1 --valued hard affiliation functions is to functions that can assign soft affiliation values in R. Letting x denote the set of all indicator functions of the form 1u for subsets U E [N], we can formally define soft affiliation models as follows.
Definition 3.1. A set Q of functions q : [N] + R that contains X called a soft affiliation model. Definition 3.2. Let d E N, and let Q be soft affiliation model. We define [Ω] C RNNN x RRND to be the set of all elements of the form (rqqT,q) ,qfT) ) with q E Q E RR and f E RD. We call [Ω] the soft rank-1 intersecting community graph (ICG) model corresponding to Q Given K N, the subset [Q) k of R. NNN x NDD of all linear combinations of K elements of [Q] is called the soft
rank-K ICG model corresponding to Q
ICG models can be written in matrix form as follows. Given K, D E N, any intersecting community granhl (C, P) E NxN x RND in [Ω] can be represented by a triplet of community affiliation matrix Q N community magnitude vector r E IR and community feature matrix F E I KDD, In the matrix form, (C, P) E [Q]x if and only if it has the form
C Q diag(r) and P= QF:
where diag(r) is the diagonal matrix in gK x with r as its diagonal elements.
3.2 The Semi-Constructive Graph-Signal Weak Regularity Lemma
The following theorem is cemi-constructive version of the Weak Regularity Lemma for intersecting communities. It is exist, but is given the result of optimization problem with "easy to work with" loss, namely, the Frobenius norm error. The theorem also extends the standard weak regularity lemma by allowing soft affillitions to communities instead of hard affiliations. For comparison to previously poposed constructive regularity lemmas see Section 7
in the sense that the approximating graphon is not just assumed
Theorem 3.1. Let (A, S) be a D-channel graph-signal of N nodes, where deg(A) E'. Let K E N, 8 > O, and Q be a soft affiliation model. Consider the matrix-signal cut norm with weights a, B 2 0 not both zero, and the matrix-signal Frobenius norm with weights (I X)II= :=
Va
N2
B ? B X
le. Let m be sampled uniformly from [K], and let R 2 1 such that K/ R E N.
Then, in probability
&/ (with respect to the choice of m) every (C*, PP) E 10m.
if () - (C", Irr S (1 1 6) min (C.P)E(O) m
[I(A,)) (C, P)
3N
R
then [|(A - (C*, "C'''" S
+ 6.
(6)
2/
2
E
K

---

The proof of Theorem 3.1 is given in Appendix B where the theorem is extended to graphon-signals Theorem means that we need not consider a complicated algorithm for estimating cut distance. Instead, we can optimize the Frobenius norm, which is much more direct (see Section 4.. The term å describes the stability of the approximation, where a perturbation in (C", Pr) that corresponds to a small relative change in the optimal Frobenius error, leads to a small additive error in cut metric.
3.3
Approximation capabilities of ICGs
ICGs vs. Message Passing. Until the rest of the paper we suppose for simplicity that the degree of the graph E' is equal the number of edges E up to a constant scaling factor 0 7 S
namely E² E. Note that this is always true for unweighted graphs, where 7 = 1. The bound in Theorem 3.1 is closer to be uniform with respect to N the denser the graph is (the closer E is to N²). Denote the average node degree by d = E/N. To get meaningful bound in (6), we must choose K N²/E. On the other hand, for signal processing on the ICG to be more efficient than message passing, we require K < d. Combining these two bounds, we see that ICG signal processing guaranteed be more efficient than message passing for any graph in the d² N (or equivalently E > N3/2).
regime:
Essential tightness of Theorem 3.1 In 12. Theorem 1,2] it was shown that the bound (6) is essentially tight in the following sense" There exists universal constant e (greater than 1 1/2312) such that for any N there exists an unweighted graph A E R. x.N with (eg(A) = E, such that any B NxN
that approximates A with error | B I S 16 must have rank greater than e N² In words,
E
there are graphs of E edges that we cannot approximate in cut metric by any ICG with K < N² Hence, the requirement K >> N²/E' for small cut metric error in (6) for any graph is tight.
E
ICGs approximations of sparse graphs. In practice, many natural sparse graphs are amenable to low rank intersecting community approximations. For example, simplistic model for how social networks are formed states that people connect according to shared characteristies (i.e. intersecting communities), like hobbies, occupation, age, etc [1]. Moreover, since ICGs can have negative community magnitudes rk,, one can also construct heterophilic components (bipartite substructures) of graphs with ICG Hence, social network can be naturally described using intersecting communities, even with K < N²/ /F. For such graphs, ICG approximations are more accurate than their theoretical bound (6). In addition, Figure F in Appendix [ shows that in practice the Frobenius local minimizer, which does not give a small Frobenius error, guarantees small cut metric error even K < N2/E. This means that Frobenius minimization is practical approach for fitting ICGs also for sparse natural graphs. Moreover, note that in the experiments in Tables 2 competitive performance with SOTA message passing methods.
and I we take K < N2/ and still get
4 Fitting ICGs to graphs
Let fix the soft affiliation model be all vectors g [0, [0,1]* In this subsection, we propose algorithms for fitting ICGs to graphs based on Theorem 3.1
4.1 Fitting an ICG to graph with gradient descent
In view of Theorem 3.1 fit a soft rank-K ICG a graph in cut metric, we learn triplet Q E [0, N|N r E and F E KxX that minimize the Frobenius loss:
L)Q,,, = A| Q diag(r) l| + + QFII
where A E R is a scalar that balances the two loss terms. To implement Q E [0, 1| in practice, we define Q Sigmoid( (R) for learned matrix R E N
Suppose that A is sparse with K2, Kd < N. The loss 7 involves sparse matrices and low rank matrices. Typical time complexity of sparse matrix operations is O(E), and for rank- K matrices it
"We convert the result of (2) to our notations and definitions.
'Two sets of nodes (parts) U4 E [A] with connections between the parts not within the parts can be represented by the ICG (1 1u17 1v17).
5

---

is O(N22). Hence, we would like to derive an optimization procedure that takes O N + E) operations. However, the first term of (7) involves a subtraction of the low rank matrix Q diag(r) from the sparse matrix A, which gives a matrix that is neither sparse nor low rank. Hence, naive optimization procedure would take (N2) operations. The next proposition shows that we can write the loss 7 in form that leads a D + E) time and OKKN + E) space complexities. Proposition 4.1. Let A = (ai5) be an adjacency matrix of a weighted graph with E edges. The graph part of the Frobenius loss be written as
| A Q diag(r))
Tr ((Q)
Q) diag(r)) (liii()(r) + |A
2
N
2
Qs.: diag(r) (Q").. 0z.j-
N
E=
JEN(S
Computing the right-hand-side and its gradients with respect Q and r has a time complexity of O(K2N + KE), and space complexity of O + E).
The proof is in Appendix We optimize Q and F using gradient descent (GD) on 7 implemented
via Proposition 4.1 After convergence, we further refine by setting = Q" p.
4.2 Initialization
In Appendix [D] we propose a good initialization for the GD minimization of 7 Suppose that K divisible by Let KK/3 E Nx/33 be the matrix consisting of the leading eigenvectors of A as columns, and A/33 E RK/33K/3 the diagonal matrix of the leading eigenvalues. For each eigenvector & with eigenvalue X, consider the three soft indicators
Φ+
Φ
Φ + Φ
Φ
11,+ Φ
(8)
11 +
with community affiliation magnitudes r = 2A 1>
12 2A || 12c and f3
-x + --1 respectively. Here, Φ+ is the positive or negative part of the vector. One can now show that the ICG C' based on the K soft affiliations corresponding to the leading K/3 eigenvectors approximates A in cut metric with error -1/22))). Note that computing the leading eigenvectors is efficient with any variant of the power iteration for sparse matrices, like any variant of Lanczos algorithm, which takes OEE) operations per iteration, and requires just a few iteration due to its fast super-exponential convergence 47 We moreover initialize F optimally by F = Q.S.
4.3 Subgraph SGD for fitting ICGs to large graphs
In many situations, we need to process large graphs for which E is too high to read to the GPU memory, but NK is not. These are the situation where processing graph-signals using ICGs is beneficial. However, obtain the ICG we first need optimize the loss 7 using a message-passing type algorithm that requires reading E edges to memory. To allow such processing, we next show that one can read the E edges to shared RAM (or storage), and at each SGD step read to the GPU memory only random subgraph with M nodes.
At each interation, we sample M < N random nodes n := (Am))= uniformly and independently from [N] (with repetition). We construct the sub-graph A (m) E RRM with entries d.j = an.ayy
M
and the sub-signal S(n) E MRMxX with entries (1)) = 8n;- We similarly define the sub-community
affiliation matrix (m) E [0, 1] i] with entries qi,) qn..j- We consider the loss
(n)
(9) which depends on all entries of F and r and on the entries of Q. Each SGD updates all of the entries of F and r, and the n entries of Q by incrementing them with the respective gradients of (m) Q" r. F). Hence, VoL (Q(()) r. F) may only be nonzero for entries qn with n E n. Proposition E in Appendix E shows that the gradients of (m) approximate the gradients of L. A More concretely, N VQ L
((m) (Q)((Q r, F) A (n) ((m) (
(n) | + + - ((())) diag(r))
(n) V L, (,) x V,L, and (()))) z V Note that the stochastic gradients with respect to Q ()) approximate scaled version of the full gradients.

---

5 Learning with ICG
Given graph-signal (A, and its approximating ICG (C, P), the corresponding soft affiliations Q = (qk) )== represent intersecting communities that can describe the adjacency structure A and can account for the variability of S. In a deep network architecture, one computes many latent signals, and these signals typically correspond in some sense to the structure of the data (A, S). It is hence reasonable to put a special emphasis on latent signals that can be described as linear combinations of (qx) Next, we develop signal processing framework for such signals.
Graph signal processing with ICG. We develop signal processing approach with ((N com- plexity for each elemental operation. Let Q E IR-Nx x be a fixed community matrix. We call R D the node space and K the community space. We process signals via the following operations:
Synthesis is the mapping F + QF from the community space to the node space, in O(NKD).
Analysis is the mapping S + Q' S from the node space to the community space, ())
Community processing refers to any operation that manipulates the community feature vector F (c.g.. an MLP in which a linear operator requires KD x KD parameters or a Transformer) in D²) operations.
Node processing is any function θ that operates in the node space on nodes independently via @(S) := (0(s))) where 0 RD + DRD' (e.g., an MLP) takes O(DD') operations. Node processing has time complexity of O(NDD'.
Analysis and synthesis satisfy the reconstruction formula Q'QF = F. Moreover, QQ'S is the projection of S upon the space of linear combinations of communities {QF F E RK Note that when A is not low rank, since Q is almost surely full rank when initialized randomly, the optimal configuration of Q would avoid having repetitions of communities, as this would unnecessarily reduce its rank. Therefore, Q is typically full rank, and in this generic case Q = (Q Q)
Deep ICG Neural Networks. In the following, we propose deep architectures based on the elements of signal processing with an ICG, which take ( K + K2D + D)) operations each layer. In comparison, simplified message passing layers (e.g.. GCN and GIN), where the message is computed using just the feature of the transmitting node, have a complexity of O(ED + ND²). General message passing layers, which define messages via a function applied the concatenated pair of node features of each edge, take O (² operations for MLP message functions. Therefore, ICG neural networks are more efficient than MPNNs if K < Dd, where d is the average node degree.
We denote by D(6) the dimension of the node features at layer E and define the initial node repre- sentations H (0) S and the initial community features (r()- = -²S.. The node features at layers 0 OSE E L - 1 are defined by
(e+1)
(0 (HO + + (F(O) wo)
F(++1) = 1'H
where θ is a neural network (i.e. multilayer perceptron or MultHHeaAAttention), w( w!! RD x)(++) are learnable matrices acting signals in the node space, and a is non- nin-linearity. We call this method ICG neural network (ICG-NN). The final representations H(L) can be used for predicting node-level properties.
We propose another deep ICG method, where F(O) E K are taken directly as trainable parameters. Namely,
((+1)) =o (H( (FFOO())
We call this method ICG,-NN for the unconstrained community features. The motivation that (()() exhausts the space of all signals that are linear combinations of the communities. If the number of communities is not high, then this is low dimensional space that does not lead to overfitting in typical machine learning problems. Therefore, there is no need to reduce the complexity of F()) by constraining it to be the output of neural network θ on latent representations. The term Q (() can hence be interpreted as a type of positional encoding that captures the community structure.
ICG-NNs for spatio-tempore graphs. For a fixed graphs with varying node features, the ICG is fitted to the graph onc Given that there are T training signals, each learning step with ICG-NN takes
"e either ignore the signal in the loss, or concatenate random training signals and reduce their dimension to obtain signal with low dimension D. This signal is used as the target for the ICG.
7

---

(( + D)) rather than O(TED²) for MPNNs. Note that T does not scale the preprocessing time. Hence, the time dimension amplifies the difference efficiency between ICG-NNs and MPNNs.
Experiments
We empirically validate our methods with the following experiments:
Runtime analysis (Section 6.1): We report the forward pass runtimes of -CG,,NN and GCN 30)
empirically validating the theoretical advantage of the former. We further extend this analysis in Appendices |+7 and F.8
Node classification (Appendix F.1 We evaluate our method on real-world node classification
45 36,, observing that the model performance is competitive with standard approaches. Node classification using Subgraph SGD (Section 6.2 and Appendix F33 We evaluate our subgraph SGD method (Section 4.3) to identify the effect of sampling on the model performance on
datasets 43
the tolokers and Flickr datasets 43
65
We find the model's performance to be robust tolokers
and state-of tatt---rrtttttttteee on Flickr.
Spatio-temporal tasks (Section 6.3
We evaluate ICGG,-NN on real-world spatio-temporal tasks [S and obtain competitive performance to domain baselines.
Comparison to graph coarsening methods (Appendix F22:
We provide an empirical comparison
between ICG-NNs and variety of graph coarsening methods on the Reddit [3 and Flickr [65 datasets, where ICG-NNs achieve matte-of-the-arr performance.
Additional experiments: We perform an ablation study over the number of communities (Ap- pendix (:44) and the choice of initialization in Section 4.2] (Appendix (F.6). We moreover experimen- tally demonstrate a positive correlation between the Frobenius error and cut norm error as hinted
by Theorem 3.1 (Appendix F.5 and perform a memory allocation analysis (Appendix F.9
6.1 How does the runtime compare to standard GNNs?
ERín, ER(n,p(n) - 0.5)
Setup. We compare the forward pass runtimes of our signal processing pipeline (NCG,,NN) and GCN (30 on Erdös-Rény: Rénni ER(n, p(n) = 0.5) graphs with up 7k nodes. Node features are independently drawn from U [0, 1] and the initial feature di- mension is 128. Both models use hidden dimension of 128, 3 layers and an output dimension of 5.
9e0 (xx)
onno
0.481672
0.9817
Results. Figure 2 reveals strong square root relationship be- tween the runtime of ING,,NN and the runtime of GCN, This aligns with our expectations, the time complexity of GCN is OEE) while the time complexity of ICG-NNs is (NN), high- lighting the computational advantage of using ICGs. We com- plement this analysis with experiments using sparse Erdös-Rényí graphs in Appendix [.7.
40
GCN time [x100
Runtime of K-ICG NN (for K=100) as function of GCN forward pass duration on graphs G ER(n, 0.5).
Figure 2:
6.2 Node classification using Subgraph SGD
tolokers
Setup. We evaluate ICG,-NN on the non-sparse graphs tolok- ers [43], following the 10 data splits of [43]. We report the mean ROC AUC and standard deviation as a function of the ratio of nodes that are removed from the graph. We compare to the baseline of MLP on the full graph.
02-
RDC AUI
80
78
(CG-NM
Results. Figure 3 shows a slight degradation of 2.8% when a small number of nodes is removed from the graph. However, the key insight is that when more than 10% of the graph removed, the performance stops degrading. These results further support our Proposition F.. in Appendix [ about the error between subgraph gradients and full-graph gradients of the Frobenius loss, option for learning on large graphs.
0.0
0.1
0.2
0.3 0.4
0. 0.9 0.V
Ratio of nodes removed
Figure 3: ROC AUC of ICG,, and an MLP as a function of the % nodes removed from the graph. and establish ICG-NNs viable
7 All our experiments are run single NVidia L40 GPU, We made our codebase available online: https://github. htt.e//www.ccoooeeeeeeeeeeeeeeaa
8

---

6.3 Spatio-temporal graphs
Setup & baselines. We evaluate ICG-NN and ICG,, NN on real-world traffic networks. METR-LA and SEMS-BAY [35] following the methodology described by [15]. We segment the datasets into windows of 12 time steps and train the models to predict the subsequent 12 observations. For all datasets, these windows divided sequentially into 70% for training, 10% for validation, and 20% for testing. We report the mean absolute error (MAE) and standard deviation averaged over the forecast- ings. The baselines DCRNN (35], Wave [60], AGCRN ()) T&S-IMP, TTS-IMP, T&S-AMP, and TTS-
Table 1: Results on dense temporal graphs. Top three models are colored by First, Second, Third.
METR-LA 0.44
PEMS-BAY
relative Frob.
0.34
DCRNN
3,22 = 0.01
1.64 = 0.00
GraphWaveNet
3.05 = 0.03
1.56 + 0.01
AGCRN
3.16 0.01
1.61 = 0.00
T&S-IMP
1.05
1,70 1 0.01
TTS-IMP
3,34
1.72 1 0.00
AMP 15 are adopted from [S] We incorporate a GRU to embed the data before inputting it into our ICG-NN models, we symmetrize the graph to enable our method to operate on it, and we disregard the features in the ICG approximation (setting x= use the Adam optimizer and detail all hyperparameters in Appendix !
T&S-AMP
0.02
1.65 0.00
AMS-AMP
1.01
1.66 + 0.00
ICG-NN
3,42 0.03
1.76 0.00
NNG
3.12 0.01
1.56 + 0.00
7 Additionally, we
Results. Table shows that ICG-NNs achieve competitive performance when compared methods that are specially tailored for spatio-temporal data such as DCRNN, Graph WaveNet and AGCRN. Despite the small graph size (207 and 325 nodes) and the low ratio of edges (graph densities of 3.54- 10 2 and 2.24 10 3), ICG-NNs perform well, corroborating the discussion in Section 3.3
Related work
We provide the main related work in this Section. In Appendix G we give an additional review.
Intersecting communities and stochastic block models. We express graphs as intersections of cliques, or communities, similarly to classical works in statisties and computer science 62.. Our approach can be interpreted as fitting a stochastic-llock-moot
(SBM) to graph. As opposed to standard SBM approaches, our method is interpreted as data fitting with norm minimization rather than statistical inference. Similarly to the intersecting community approach of BigCLAM (62), our algorithm takes (E) operations. Unlike BigCLAM, however, we can approximate any graph, as guaranteed by the regularity lemma. This is possible since ICGs are allowed to have negative coefficients, while BigCLAM only uses positive coefficients due to its probabilistic interpretation. To the best of our knowledge, regularity lemma. For a survey on SBMs we refer the reader to 322.
are the first to propose SBM fitting algorithm based on the weak
The Weak Regularity Lemma. The Regularity Lemma is central result in graph theory with many variants and many proof techniques. One version is called the Weak Regularity Lemma (for graphs 20). graphons [38], or graph-signals and graphon-signals (33), and has the following interpretation: every graph can be approximated in the cut metric by an ICG, where the error rate e is uniformly 0(2-1/2 R While (20) Theorem 2] proposes an algorithm for finding the approximating ICG, the algorithm takes N20(K) time to find this @ This time complexity is too high to be practical in real-world problems. Alternatively, since the cut metric is defined via maximization process, finding a minimizing ICG by directly optimizing cut metric via GD approach involves min-max problem, which appears numerically problematic in practice. Moreover, computing cut norm is NP-hard [3] Instead, we consider a way to bypass the need to explicitly compute the cut norm, finding K community ICG with error O(K -1/2) in the cut metric by minimizing the Frobenius norm. Here, each gradient descent step takes O OEE)) operations, and EK is typically much smaller than N2* As opposed to the algorithm in 20). our theorem is only cemi-constructive, as GD is not guaranteed to find the global minimum of the Frobenius error. Still, our theorem motivates practical strategy for estimating ICGs, while the algorithm formulated in (0) is only of theoretical significance. We note that for the Szemerédi (non-weak) regularity lemma [4]] it was shown by Alon
'In some papers the lemma is formulated for non-ontoeennn mon-intersecting blocks Σt,, ri.j Iu L0,, where UfU = (N), with error O -1)/- The intersecting community case intermediate step of the proof. 'One needs to convert the scaling of the Frobenius and cut norms used in 20 to our scaling and to follow the proof of (20) Theorem to see this.

---

et al. 4 that regular partition with enror < c into non- -on-iterssectig communities (the analogue to ICG in the Szemerédi regularity lemma) can be found in polynomial time with respect to N, provided that N is very large (N ~ 2 20 ). For more details on the Weak Regularity Lemma, see Appendix A
Subgraph methods. Learning on large graphs requires sophisticated subgraph sampling techniques 65).
for deployment on contemporary processors (24 12 13 (5). After the preprocessing step on the ICG, our approach allows processing very large networks more accurately, avoiding subsampling schemes that can alter the properties of the graph unintended ways.
GNNs with local pooling, Local graph pooling methods, c.g., 163 9 construct a sequence of coarsened versions of the given graph. each time collapsing small sets of neighboring nodes into a single "super-node." At each local pooling layer, the signal is projected from the finer graph to the coarser graph. This is related to our ICG-NN approach, where the signal is projected upon the communities. As opposed to local graph pooling methods, our communities intersect and have large-scale supports. Moreover, our method does not lose the granular/high feeeueeeernecyy content of the signal when projecting upon the communities, In pooling approaches, the graph is partitioned into disjoint, or slightly overlapping communities, each community collapses to node, and standard message passing scheme is applied on this coarse graph. In ICG-NNs, each operation on the community features has a global receptive field in the graph. Moreover, ICG-NNs are not of pressage-pasiing type: the (flattened) community feature vector F is symmetryless and is operated upon by a general MLP in the ICG-NN, while MPNNs operate by the same function on all edges.
we also have node-wise operations at the fine level.
In terms of computational efficiency, GNNs with local pooling do not asymptotically improve run- time, as the first layer operates on the full graph, while our method operates solely on the efficient data structure.
Variational graph autoencoders. Our ICG construction is related to statistical network analysis with latent position graph models (6. Indeed, the edge weight between any pair of nodes n, m in the ICG is the diagonal Bilinear product between their affiliation vectors, namely, Σ; ry Lu, (n) 1l,,, (m), which is similar to the inner produce decoder in variational graph autoencoders (29] 6]. However, as opopsed to variational graph autoencoders, we have the coefficients rj, that can be negative and hence allow a more expressive decoding.
8 Summary
We introduced an new approach for learning on large non-sparse graphs, using ICGs. We proved a new constructive variant of the weak regularity lemma, which shows that minimizing the Frobenius error between the ICG and the graph leads to uniformly small error in cut metric. We moreover showed how to optimize the Frobenius error efficiently. We then developed a signal processing setting, operating on the ICG and on the node reprsentations in O(N) complexity. The overall pipeline involves precomputing the ICG approximation of the graph in EE) operations per iteration, and then solving the task on the graph in O(N) operations per iteration. Both fitting an ICG to a large graph, and training a standard subgraph GNNs, require an online subsampling method, reading from slow memory during optimization. However, fitting the ICG is only done once, and does not require an extensive hyperparameter optimization. Then, learning to solve the task on the graph with ICG-NNs is efficient, and can be done directly on the GPU memory. Since the second learning phase is the most demanding part, involving an extensive hyperparameter optimization and architecture tuning, ICG-NN offer potentially significant advantage over standard subgraph GNNs. This gap between ICG-NNs and MPNNS is further amplified for time series on graphs.
The main limitation of our method is that the ICG-NN is fitted to specific ICG, and cannot be naïvely transferred between different ICGs approximating different graphs. Another limitation is the fact that the current ICG construction is limited to undirected graphs, while many graphs, especially spatiotemporal, are directed. One potential avenue for future work is thus to extend the ICG construction to directed graphs. Additional future work will study the expressive power of ICGs.
Acknowledgement
The first author is funded by the Clarendon scholarship. This research was supported by the Israel Science Foundation (grant No. 1937/23) and the United States Israel Binational Science Foundation (NSF-BSF, grant No. 2024660). This work was also partially funded by EPSRC Turing AI World- Leading Research Fellowship No. EP/X040062/1.
10

---

References
[1] Edo M. Airoldi, David Blei, Stephen Fienberg, and Eric Xing. Mixed membership stochastic blockmodels. NeurIPS, 2008.
[2] Noga Alon. Approximating sparse binary matrices in the cut-norm. Linear Algebra and its Applications, 2015.
[3] Noga Alon and Assaf Naor. Approximating the cut-norm via grothendieck'' inequality. SIAM, 2006.
[4] Noga Alon, Richard A Duke, Hanno Lefmann, Vojtech Rodl, and Raphael Yuster. The algorith- mic aspects the regularity lemma. Journal of Algorithms, 1994.
[5] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In ICLR, 2021.
[6] Avanti Athreya, Minh Tang, Youngser Park, and Carey E Priebe. On estimation and inference in latent structure random graphs. Statistical Science, 2021.
[7] Jiyang Bai, Yuxiang Ren, and Jiawei Zhang. Ripple walk training: A subgraph-based training framework for large and deep graph neural network. IJCNN, 2020.
[8] Lei Bai, Lina Yao, Can Li, Xianzhi Wang, and Can Wang. Adaptive graph convolutional recurrent network for traffic forecasting. NeurlPS, 2020.
[9] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In ICML, 2020.
[10] Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. Structural deep clustering network. In WWW, 2020.
[11] Christian Borgs, Jennifer T Chayes, László Lovász, Vera T Sós, and Katalin Vesztergombi. Convergent sequences of dense graphs i: Subgraph frequencies, metric properties and testing. Advances in Mathematics, 2008
[12] Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. ICLR, 2018
[13] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In KDD, 2019.
[14] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In ICLR, 2020.
[15] Andrea Cini, Ivan Marisca, Daniele Zambon, and Cesare Alippi. Taming local effects in graph-based spatiotemporal forecasting. NeurlPS, 2024.
[16] Luca Cosmo, Anees Kazi, Seyed-Ahmad Ahmadi, Nassir Navab, and Michael Bronstein. Latent- graph learning for disease prediction. In Medical Image Computing and Computer Assisted Intervention, 2020.
[17] Bahare Fatemi, Layla El Asri, and Seyed Mchran Kazemi. Slaps: Self-supervision improves structure learning for graph neural networks. In NewrlPS, 2021.
[18] Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning molecular graphs. arXiv, 2020.
[19] Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. In ICML:: Graph Representa- fion Learning and Beyond (GRL+) Workshop, 2020.
[20] Alan M. Frieze and Ravi Kannan. Quick approximation to matrices and applications. Combina- torica, 1999.
11

---

[21] Johannes Gasteiger, Stefan Weißeenbegger, and Stephan Günnemann. Diffusion improves graph learning. In NeurlPS, 2019.
[22] Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
[23] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. NewrIPS, 2017.
2017.
[24] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurlPS, 2017.
[25] Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. In KDD, 2021.
[26] Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. arXiv, 2021.
[27] 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.
[28] Anees Kazi, Luca Di Cosmo, Seyed-Ahme Ahmad Ahmadi, Nassir Navab, and Michael M. Bronstein. Differentiable graph module (dgm) for graph convolutional networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
[29] Thomas Kipf and Max Welling. Variational graph auto-encoders. arXiv, 2016.
[30] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[31] Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In ICML, 2018.
[32] Clement Lee and Darren Wilkinson. A review of stochastic block models and extensions for graph clustering. Applied Network Science, 2019.
[33] Ron Levie. A graphon-signal analysis of graph neural networks. In NewrlPS, 2023.
[34] 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. In ICML, 2022.
[35] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. In ICLR, 2018.
[36] 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. NeurIPS, 2021.
[37] László Miklós Lovász. Large networks and graph limits. In volume 60 of Colloquium Publica- tions, 2012.
[38] László Miklós Lovász and Balázs Szegedy. Szemerédi's ' lemma for the analyst. GAFA Geometric And Functional Analysis, 2007.
[39] Jiaqi Ma, Weijing Tang, Ji Zhu, and Qiaozhu Mei. flexible generative framework for graph- based semi-supervised learning. In NeurIPS, 2019.
[40] Sohir Maskey, Ron Levie, and Gitta Kutyniok. Transferability of graph neural networks: An extended graphon approach. Applied and Computational Harmonic Analysis, 2023.
[41] Raffaele Paolino, Aleksandar Bojchevski, Stephan Günnemann, Gitta Kutyniok, and Ron Levie. Unveiling the sampling density non-uniform geometric graphs. In ICLR, 2023.
[42] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv, 2020.
12

---

[43] Oleg Platonov, Denis Kuznedelev, Michael Diskin. Artem Babenko, and Liudmila Prokhorenkova.
critical look the evaluation of GNNs under heterophily: Are we re- ally making progress? In ICLR, 2023.
[44] Jiří Rohn. Computing the norm ||a|bo, np-hard. Linear and Multilinear Algebra, 2000.
[45] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 2021.
[46] Luana Ruiz, Luiz O. Chamon, and Alejandro Ribeiro. Graphon signal processing. IEEE Transactions on Signal Processing, 2021.
[47] Yousef Saad. Numerical methods for large eigenvalue problems: revised edition. SIAM, 2011.
[48] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: core-set approach. arXiv, 2017.
[49] Endre Szemerédi. Regular partitions of graphs. Stanford University, 1975.
[50] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks graphs via curvature. In ICLR,, 2022.
[51] Lloyd N. Trefethen and David Bau. Numerical Linear Algebra, Twenty-fifth Anniversary Edition. Society for Industrial and Applied Mathematics, 2022.
[52] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. NeurIPS, 2017.
[53] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[54] Petar Velivcković, Lars Buesing, Matthew Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell. Pointer graph networks. In NeurlPS, 2020.
[55] Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang. Attributed graph clustering: A deep attentional embedding approach. In IJCAI, 2019.
(56) Lin Wang, Wenqi Fan, Jiatong Li, Yao Ma, and Qing Li. Fast graph condensation with structure-based neural tangent kernel. WWW, 2024.
[57] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic graph enn for learning on point clouds. ACM Transactions on Graphics, 2019.
[58] Max Welling. Herding dynamical weights to learn. In ICML, 2009.
[59] Huijun Wu, Chen Wang. Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adver- sarial examples for graph data: Deep insights into attack and defense. In IJCAI, 2019.
[60] Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. Graph wavenet for deep spatial-temporal graph modeling. In IJCAI, 2019.
[61] Jaewon Yang and Jure Leskovec. Structure and overlaps of communities in networks. In SNAKDD, 2012.
[62] Jaewon Yang and Jure Leskovec. Overlapping community detection at scale: a nonnegative matrix factorization approach. In Association for Computing Machinery, 2013.
[63] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In NeurlPS, 2018.
[64] Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph transformer networks. In NeurIPS, 2019.
13

---

[65] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In ICLR, 2019.
[66] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen, Dataset condensation with gradient matching. arXiv, 2020.
[67] Xin Zheng, Miao Zhang, Chunyang Chen, Quoc Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan. Structure-fire free graph condensation: From large-scale graphs to condensed graph-free data. NeurlPS, 2024.
[68] Houquan Zhou, Shenghua Liu, Danai Koutra, Huawei Shen, and Xueqi Cheng. A provable framework of learning graph embeddings via summarization. In AAAI, 2023.
[69] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS, 2020.
14

---

A The weak regularity lemma
Let G (N, E be graph and P (Wi....,NN, NNc) be partition N. The partition called equipartition if | - W < for every 1 - j,j S k. For any two subsets S C N, the number of edges from 2/ are denoted by EG(U, S). Given two node set U N, if the edges between N and Nj were distributed randomly, then, the number of edges between U and S would have been close to the expected value
eo(N,,N)) =l WWII I WG
(PU =
Thus, the irregularity, which measure of how non-random like the edges between {N₃ are, is defined to be
irrega(P)
max leG(U, - - U,SCN
(10)
Theorem A.1 (Weak Regularity Lemma (20). For every O and every graph G (W,)), there an equipartition P .N, o into S 20/2² classes such that irrega (P) S e. Here, is universal constant that does not depend G and c.
The weak regularity lemma states that any large graph G can be represented by the weighted graph Go with node A NNk,, where the edge weight between the nodes N, and Ng is ec(N),NG) which depicts smaller, coarse- gaarse-graindd version of the large graph. The "large-scale" [NGIAN
structure of G is given by G and the number of edges between any two subsets of nodes Us c C. and U1 C N2 is close to the "expected value" 6p .4.). Hence, the deterministic graph G "behaves" if it was randomly sampled from the "stochastic block model" G
can shown that irregularity coincides with error cut metric between the graph and coarsening SBM. Namely, to see how the cut-norm is related to irregularity (TO), consider a graphon Wa induced by the graph G EW, Let = [Ni...... ,N,) be an equipartition of N. Consider the graph G defined by the adjacency matrix A (a W with
eG(NN,
p = W.g.l, Nag
where Nq. E P is the class that contains node i. Now, it can be verified that
I[a - WGr la = (P)
Hence, the weak regularity lemma can be formulated with cut norm instead of irregularity.
B Graphon-Signal Intersecting Communities and the Constructive Regularity Lemma
In this section we prove constructive weak regularity lemma for graphon-signals, where Theorem 3. a special case. We start by defining graphon-signals in Subsection B. We define graphon-signal cut norm and metric in Subsection [.2] and graphon-signal intersecting communities in [..] In
Subsections B.4 and B.3 we formulat late and prove the constructive graphon-signal weak regularity
lemma. Finally, Subsection B.6 we prove the constructive graph-signal weak regularity lemma special case.
For m.J N, the L2 norm of a measurable function
(fi
[0, 11 R where
fs [0, 11 + R, defined to |lIl|2 = V So.1j [f,())) dxc
B.1 Graphon-signals
A graphon
II 37 can be seen as a weighted graph with a "continuous" node set (0. 1]. The space
of graphons W defined to be the set of all measurable symmetric function W : [0, 1]2 - [0, 1). W (z W W(y, x). Each edge weight W W(z, y) E [0, 1] of graphon W W can be seen as the
15

---

probability of having an edge between nodes z and y. Graphs can be seen as special graphons. Let I,, = ( } be an interval equipartition: a partition of [0, 1] into disjoint intervals of equal length.
graph with adjacency matrix A (au.)) induces the graphon WA. A, defined by WA Wa(z.))
[[zm] [ym] Note that Wa A piecewise constant on the partition Im. We hence identify graphs with their induced graphons. graphon also be seen
generative model of graphs. Given a graphon W, a corresponding random graph is generated by sampling i.i.d. nodes {un) from the graphon domain [0, 11, and connecting each pair un Um in probability W (Un, Um) to obtain the edges of the graph.
The space of grahon-signals is the space of pairs of measurable functions (W, s) of the form W. [0, 1]a [0, and s [0, 1] > [0, 1jD, where D N is the number of signal channels. Note that datasets with signals in value ranges other than [0, 1] can always be transformed (by translating and scaling in the value axis of each channel) to [0, i -aauued Given a discrete signal S [N] -
[0, 1] we define the induced signal 8ş over [0, 1] by ss(#) 8 [[m]] We define the Frobenius distance between two graphon-signal (W, and (W", s') simply their Lz distance, namely,
D
I[W,s))(W' s) - (W", s') = || wI
+
> j=1
8. - 1'11
(11)
for some a, > 0.
B.2
Cut-distance
The cut metric is natural notion of graph similarity, based the norm. The graphon-sigh signal cut norm was defined in [33), extending the standard definition to graphon with node features. Definition B.1. The graphon cul norm W [2, 1)2 is defined to be
1/// W(x: (xx y)dzdy S
[Wll= = sup
(12)
The signal cut norm of s (81,..., ) (L210, 1I) is defined to be
1 D || = D
1 (x))d
Σ
sup UC(0,1]
(13)
j=1
The graphon-signe cut norm of (W,s) E L0 1|2 (L3 1)) with weights 0 and 3 > 0, is defined to be
[[W, sl W ll + 3 ||||
(14)
Given two graphons W, W their distance in cut metric is the cut norm of their difference, namely
I - Wilb = sup 1 / (W(z,0) W' u) drdy
(15)
s,Tc
The hight-hand-side of 15 is interpreted the similarity between the adjacencies W and W on the block on which they are the most dissimilar. The graphon- cut metric is similarly defined to be [I s) (W", lo) The cut metric between two graph-signat is defined to be the cut metric between their induced graphon-signals.
In Subsection B.6 we show that the graph-signal cut norm of Definition 2.1 are special case of graphon-signal cut norm for induced graph-signals.
B.3 Intersecting community graphons
Here, we define ICGs for graphons. Denote by x the set of all indicator function of measurable subset of [0, 1]
(1u
u C [0, 1] measurable).
IIn the definition of WA. the convention is that [0] = 1.
16

---

Definition B.2. A set Q of bounded measurable functions q [0, 1] - R that contains is called soft affiliation model.
Definition B.3. Let D E N. Given soft affiliation model Q. the subset [Ω] of L2 1J (L 1 of all elements of the form (rg(æ) I((), by(2)), with q E Q. r E R and b E IRP called the soft rank-1 intersecting community graphon (ICG) model corresponding to Q. Given K E N, the subset [Q]x of L, 1]2 x (L2(0, 1)) of all linear combinations of K elements of [Ω] is called the soft rank-K K ICG model corresponding to Q. Namely, (C,p) [Ω] if and only if it has the form
K
K
C(r, v) = Σ
(2)x()))x()) and p(z) = Σ bx)x(2)
k=1
for (g)) E QK called the community affiliation functions, (rx) E E called the community
affiliation magnitudes, and /K E KxD called the community features.
B.4
constructive graphon-signal weak regularity lemma
The following theorem is the semi-constructive version of the weak regularity lemma for intersecting communities of graphons. Recall that a and denote the weights of the graphon-signal norm
(4).
Theorem B.1. Let D E N. Let (W,s) be a D-channel sraphon-signal K N, 8 > O. and let be a soft indicators model. Let m be sampled uniformly from [K], and let R 2 1 such that K/R R E N.
Consider the graphon-signal Frobenius norm with weights Va [[]][ 3 E ||s Then, in
probability शे. (with respect to the choice of m), for every (C* ,p") E [0]m.
if II(W, s) - (C*,p")ll= 5 (1+ min IIW,s) (C, p)ll (C.P))()),
then (1(W,)) (C",p")l
(₂ v Q aB 11sll
R K
Va + 8 11
5.
B.5
Proof of the soft constructive weak regularity lemma
In this subsection we prove the constructive weak crophon-signll regularity lemma.
B.5.1 Constructive regularity lemma in Hilbert spaces
The classical proof of the weak regularity lemma for graphons is given in 38 corollary of a regularity lemma in Hilbert spaces. Our goal is to extend this lemma to be constructive. For comparison, let us first write the classical result, from [3 Lemma 4], even though we do use this result directly.
The lemma is
Lemma B.2 (38)), ). Let KA, K2,... be arbitrary nonempty subsets (not necessarily subspaces) of real Hilbert space H. Then, for every >> 0 and H there is S [1f67 and (fa E K2a) and (74 E R) p. such that for every w E Km+11
)
s
|| I|lll-
(16)
Next, we show how to modify the result to be written explicitly with an approximate minimizer of Hilbert space norm minimization problem. The proof follows the step of (38) with some modifications required for explicitly constructing approximate optimizer.
Lemma B.3. Let (KC)jen be a sequence of nonemply subsets of a real Hilbert space H. and let
8 2 O. Let K > 0, let R 1 such that KJ / R E N, and let E H. Let m be randomly uniformly sampled from [K]. Then, in probability R (with respect to the choice of m), any vector of the form
g"
fifa
such that
7 (75)72 R and f=(1) EK
X Km
j=1
17

---

that gives close-to-best Hilbert space approximation of in the sense that
- (1 8) inf where the infinum is over Y R and E Kn x... Kin also satisfies
11g
Σ
Afill
(17)
7.
2=1
R Vw E Km+1, kw,g gg = Ioll Melll V
+
K
Proof. Let K > O. Let R 2 such that K/R E N. For every k, let
Tk = (1 + 5) inf lgg
Σ afll?
7.
where the infimum is over 7 = {yi..... 7 E R and = (f...... f&e E K2 x ... x Kg. Note
that ||a|1 2 + I+d 2 2 0. Therefore, there is subset of at least (1 # ) + indices
K indices m in [K] such that m in [K] such that 7m S Mm+1 + R0+6 |lall Otherwise, there are π R(1+6)
|gll which means that
1m++1 < 7/m
K RRI+ 6)
s1+ (1 8) 11g11
JKK 7
K
which is a contradiction to the fact that VIK 2 0.
Hence, there is set M C [K] of (1 H) indices such that for every m E M, every
m
g"
2 j=1
fsfs
(18)
that satisfies
1g 9²1l² $ 7m
also satisfies
(1 O ||g11
[gg - 9-"g" g² S 7m+ +
(19)
K
Let E KCm11 By the definition of 7m+1, have for every t R,
11g g0 R l1a11
- (g" + tw)ll
7m+11
1
1+8
This can be written Vt E IR, The discriminant of this quadratic polynomial is (w. g -² || (x
|| 12 2 (w,9 g") t
l +
) 11g =²1222 0.
(20)
K
1 1
R
|llll
+
1 + 8 11g 9²ll²)
and it must be non-posten non-positive satisfy the inequality
20
namely
R
(w. - g² < |1/1/
||
(1
llg - 112
K
1 + 8
R
< 4 ||
||
+ (1
)mm
K
+ 8
R
1
< 4 |
||
+
(1
(1 + 6) ||all
K
+
8
which proves
R
(w, g 9²)
||||| |لو||
6.
K
This is also true for -w, which concludes the proof.
18

---

B.5.2 Proof of the Soft Constructive Weak Regularity Lemma for Graphon-Signals
For two functions f.g: [0, - IR, we denote by f g [0, 1/2 - R the function
f @ g(, y) = (z))((v)
We recall here Theorem B.1 for the convenience of the reader.
Theorem B.1, Let (W,s) s) be a graphon-signal, K E N, > O. and let Q be a soft indicators model. Let m be sampled uniformly from [K] and let R 2 1 such that K/R R N. Consider the
graphon-signe signal Frobenius norm with weights Va [W]] 3E |syyl Then, in probability
1 R (with respect to the choice of for every (C", pp) E (2)m.
if II(W, s) (C" S (1+6) min (C.))((),
([W,,) (C,p
then I1(Ws) (C*,
3 a² W aB [|l1|
R K
a 82 1111/pp
5.
The proof follows the techniques of part of the proof of the weak graphon regularity lemma from [8]. while tracking the approximate minimizer our formulation of Lemma [B.]] This requires probabilistic setting, and extending soft indicators models. We note that the weak regularity lemma in (38] is formulated for non-intersecting blocks, but the intersecting community version an intermediate step in its proof.
Proof. Let use Lemma
B.3 with [.2 112 (I210, 1)) with the weighted inner product
D
((W,s), .()) = a Jf W(x, WWr, ydddy + +B²
Σ #=1 0.1)
(z)))s)(z)dd,
and corresponding norm V a W + E, ||, and corresponding weighted inner product, and K,, = [Ω]. Note that the Hilbert space norm is the Frobenius norm in this case. the setting of the lemma, we take g (W,s) s). and 9" [Q] By the lemma, in the event of probability 1 - 1/R. any approximate Frobenius minimizer (C" .p"). namely, that satisfies [[(W,)) - ,p") S (1 + 6) min(c.))e(@).. 3I(W,s) (C,p)]lF, also satisfies
R K
((T, (W, s) (C*, p²)) [IT,, (I,, /
+
for every (T,y) E [Q]. Hence, for every choice measurable subsets S, T C [0, 1], we have 1 (W (2, y) - C* (x, drdy
2 / / (w v) C* dodd + f (W v) O*t d)dd
I (
JSUT (W v) - C* (x. d))dddy
(W(x,)) - C² ("(,,y)) )rdd
2 SUT
(W v) - Cx, drdy
1 ((1s (0 1s, 1s, (W, (C*, ,(',,"')))
< 2a
(C", ((1 & 1 -W,*)-(C* (r)))"))
+
2a
+ 2a
((17 @ 17, 17,00, (W, - (C*,p")
R
< 2a
(W, s)]rr [1 [|(1s.T @ ISuT, 0) + [[(1s @ 1s, + |1(1 x 17. 17100| )
< 2a
3
||]
W| + 1111b11p Val
R
+
K
19

---

Hence, taking the supremum over S, T C [0, 11, we also have
3 a2 afllwil + aB || K
R
a - -
+ 6.
Similarly, for every measurable T с [0, 1] and every standard basis element b = (8 for any
j E [D].
(8)(x) - pz(2))
3 ((0, b1,), (W,s) (C* ,p'))
R
S 3
I(W, s) (r
+
K
1
$ V |||l + | BV
8,
8
K
so, taking the supremum over T C [0. 1] independently for every E [D], and averaging over j E [D], we get
R
-11s-p'lla s
/a31 B 11 K
+
Overall, we get
3 - (C",p")la - ( @2 + a [111 + o 12
R K
+
B.6 Proof of the constructive weak regularity lemma for sparse graph-signals
We now show that Theorem 3.1 is special case of Theorem B. restricted to graphon-signals induced by graph-signals, up to choice of the graphon- signal weights a and B. Namely, choose a 2 E and B = 5' with a' + 3 = 1 as the weights of the graphon-signal cut norm of Theorem B. with arbitrary a', B' 2 0 satisfying a' + 3 1. It is easy to see the following relation between the graphon-signal and graph-signal cut norms
[I(W A. ss) (War, (p-))ln ((A, (C", P')
where [|A, - (C*, P' P') Ila based on the weights a' and 3'. Now, since
deg( A) A)/N2 ||A|| N2. and by ||S||p I 1, the bound in Theorem B.1
becomes
3 2
N
E
N2 3
N2 E
R K
[1,A, S) (C)EEEE
2
2
V
+ 3/2
+ 8
E
N2
E
E
N2
N
SC
+5
VEL
K
where, since a' + B' = 1, and by convexity of the square root,
C 2 Va' + VB < Va' + /VBr <
3
3 /va' 2
3
The only thing left to do is to change the notations a' a and 3' + 3.
C Fitting ICGs to graphs efficiently
Here, prove Proposition For convenience, we recall the proposition.
20

---

Proposition 4.1.
Let A = (a=ي)āāj=1 be an adjacency matrix of weighted graph with E edges.
The graph part of the Frobenius loss can be written as
| A Q drag(r)
Tr ((Q) Q) diag(r) diag(r) + +Al
N
N
2
Qi diag (r) (Q") :i Di,j-
N2
JEN()
Computing the right-hand-side and its gradients with respect Q and r has a time complexity of O(K"N + E), and space complexity of OKKN E).
Proof.
The loss can be expressed
A - Q diag(r))
1
Σ
Qi, diag(r) (QT)..)²
N
b1=1
N
Σ jEN(()
Ci.j Qi diag(r) (Q ).a)) + Σ (-Qu: drag(r) (Q (Q)).)
N2
iml
SEN(()
N
Σ
Oi,j - Qi: diag(r) (Q (Q).))
2 +
N
JEN((()
Ur diag(r) (Q (.))
Σ diag(r) (Q (Q))
+
jEN(()
We expand the quadratic term (a.s Qt. diag(r) (Q)) and get
A Q diag(r))
2
diag()))))
(Q
[a - 2Q,, (Q").. ai.))
N
(=1 jeN(()
N
Q (iagg())7)
2
Σ
Qu. diag(r) (QT)., as,5
a.jj
N2
N2
1==1
JEN(()
N
Tr (Q diag(r) diag(r)
af
N
N
f,=1
2
Qui diag(r) (QT).. digj
N2
JEN(1)
N
1
Tr (Q Q diag(r) Q diag(r)) +
E of
N2
N2
ij=l
2
Qi. diag(r) (QT)., Oi,j JEN(()
N2
The last equality follows the identity VB, D E RNK Tr(BDT) = TT(D B), with B Q Q Q diag(r) and = Q
The middle term in the last line is constant and can thus be omitted in the optimization process. The leftmost term the last line is calculated by performing matrix multiplication from right to left, or by first computing Q Q and then the rest of the product. Thus, the time complexity is
21

---

O(K2N) and the largest matrix held in memory is of size N).. The rightmost term is calculated by passsgg-passsing which has time complexity of E). Thus, Computing the right-hand hand-side and its gradients with respect to Q and r has a time complexity of O(K2N + KF) and space complexity of O(KN+ + E).
D Initializing the optimization with eigenvectors
Next, we propose a good initialization for the GD minimization of For that, we consider corollary of the constructive soft weak regularity for grapohns, with the signal weight in the cut norm set to 3 0, using all L [2 1] functions as the soft affiliation model, and taking relative Frobenius error with = O. In this case, the best rank- K approximation theorem (Eckart- Yoon--ouugg--ssn Theorem [31] Theorem 5.9I), the minimizer of the Frobenius error is the projection of W upon its leading eigenvectors. This leads to the following corollary.
Corollary D.1. Let A E [0, 1 be a matrix with deg( (Ag(()) N2 || E'. Ler K E N. let m be sampled uniformly from [K], and let 2 such that K/R E N. Let ......, Rm be the leading eigenvectors of A, with eigenvalues . Am of highest magnituess [>1 2 122) .... 2 12mb and let C = => k==1 AL Then, in probability - 1 (with respect to the choice of m),
3N
R
A - C* 1O,N,E S
E'
K
The initialization is based Corollary D.1 as follows. We consider the leading K/3 eigen- vectors, assuming K is divisible by 3. for reasons that will become clear shortly. Hence, for C 1k//AK//5 DT K/3 where 4x/3 E Nx/3 the matrix consisting of the leading eigenvectors of A as columns, and A Ak/3 IR K/3xX//3 the diagonal matrix of the leading eigenvalues, we have
3N
3R
| C'Io,NE, <
(21)
EVE'
K
To obtain soft affiliations with values in [0, 1], we now initialize Q as described in
E Learning ICG with subgraph SGD
In this section we prove that the gradients of the subgraph SGD approximate the gradients of the full GD method.
Proposition E.1. Let < p < 1. Under the above setting, if we restrict all entries of C, P, Q.Q. and F to be in [0, 1J. then in probability at least 1 p. every k E [K], d E [D] and m [M]
gamik L
M
V
((n
2 (1/s) + 2 2og N) + 2 log (K) 2 log(22
N
qmm
N
M
2 log((1/p)) + 2og (N) + log (K) + 2 (2)
VrLL- Vr, (m))
S V
M
4A
2log Alog(1/p2)) + 2og () + 2 2 D) + (2)
V Vl V ViaaL (m))
D
M
Proposition E.1 means that the gradient with respect r and F computed each SGD step approximate the full GD gradients. The gradients with respect to Q approximate a scaled version of the full gradients, and only on the sampled nodes, where the unsampled nodes are not updated in the SGD step. This means that when optimizing the ICG with SGD, we need to scale the gradients with resect to Q of the loss by M To use the same entry-wise learning rate SGD as in GD one must multiply the loss (9) by M/N. Hence, SGD needs in expectation N/M times the number of steps that GD requires. This means that in SGD we trade the memory complexity (reducing it by factor M/N) by time complexity (increasing it by factor N/M). Note that slower run-time, while not desirable, can be tolerated, while higher memory requirement is often prohibitive due to hardware limitations.
22

---

From here until the end of this section we prove Proposition E.1 For that, we compute the gradients of the full loss L and the sampled loss (mm)
To avoid tensor notations, treat by abuse of notation the gradient of function
linear operator.
Recall that the differential D.T = (r'T(r') of the function T g + R at the point E E the unique linear operator R R that describes the linearization of T about r' via
T(r' + err") T(r)) + eD,Tr" + o(E)
where E R. Given an inner product in RR, the gradient v,T V,T(r') RU*E of the function T: R + Rd the point r' RR is defined to be the vector (guaranteed to uniquely exist by Riesz representation theorem) that satisfies
D,Tr" (r", V,T)
for every r" E R. Here, the inner product if defined row-wise by
v,T) == ((r", V,T )
where [(u, the u-th row of V,T. In our analysis, by abuse of notation, identify V.T with D,I for a fixed given inner product.
Define the inner product between matrices
(B, D) Diggdes
2,
Denote
LCC, P) = |A - C + +115 Pll
First, the gradient of ||A - C with respect to C is
Vc - - CI = N² (A CA-C),
which is identified by abuse of notation by the linear functional Ig.N² - R
(A C7) N2
2
D --VAllA-CT (D) D,
Similarly,
2
V = ND (S - P) ND
R.
Given any parameter z E R on which the graph C (zz) and the signal P P(z) depend, have
2
V.I(C,P) = N² (C (C AVV, ND PP SJV.P,
(22)
where V.C R + N² and V.C E R + RDD are linear operators, and the products in are operator composition, namely, coordinates is elementwise multiplication (not matrix multiplication.
Let now compute the gradients of C diag(r) and P QF with respect Q, and F in coordinates. We have
Vr = fi
and
Aym G.j T + T
where 6, is 1 if and zero otherwise. Moreover,
SnaPi,d -i,
and
mm. Pi,d fk.ddi-m
23

---

Hence,
2
V 1. =
(Gr 04d 0a.))aa
N2
w==1
N
2
2
V
L
Cm. Um M [k 4j +
Cimm - -i..m
Pmmdd 8m Sm,d
0m,k
N j=1
N2
ND
d=1
and
2 ND
V Sn. 1
(1i 81.1)
Similarly,
V L (n)
2
(Coimn aniing Mo,,
M
w/1
V Amm (mn)
2
Cnm am my )cu
M
M
+
(Cng.mo Pm
an Cunln + A MD
Σ d=1
(Pmmd a
M
and
M
fay (m)) = MD
Σ
(Paid 8yg 1.)
1=1
We next derive the convergence analysis, based on Hoeffding's Inequality and two Monte-Carlo approximation lemmas.
Theorem E.2 (Hoeffding's 's Inequality). Let Y1,..., S Ym < b almost surely. Then, for every lo > 0.
.....,y Yıs be independent random variables such that
P Em - E[Ym)) 2 2k) s exp (-
2k M
(b (b- a)
The following is standard Monte Carlo approximation error bound based Hoeffding's inequality.
Lemma E.3. Let (im LM be uniform i.id in [N]. Let v E N be vector with entries vn in the set 1]. Then, for every 0 < p < 1, in probability at least 1 -
1 M
Σ
1
2log(1/p) 2 log(2)
Un
S
M
Proof. This a direct result of Hoeffding's Inequality on the i.idd. variables (V:... M mmm--
The next lemma derives Monte Carlo approximation error bound based on Hoeffding's 's inequality for 2D arrays, in case one samples only 1D independent sample points, and the sample points are all pairs of the 1D points (which are hence no longer independent).
Lemma E.4. Let (im Jm=1 be uniform i.i.d in [N]. Let A E N be symmetric with az, E [1-1,1] Then, for every p <, 1, in probability more than -
IM
N
N
M
M
2 2log(1/p) 2log(N) (N) + log(2)
aj.
a aim
< 2
N
M
M
n=1
TA
1=1
24

---

Proof. Let 0 < P < 1. For each fixed n E [M], consider the independent random variables
Ym ii with
N
1
B
jnm
N
==1
and - y. I 1. By Hoeffding's Inequality, for k log(1/p) N2)
we have
M
Σ
j
aimmn
S k
N
M
in event &, of probability more than
p/N. Intersecting the events { Inmls get
N
M
Vn E [N]
1
jjnn
Σ
S
N
M m=1
in the event & n, probability at least the event 3
p. Hence, by the triangle inequality, also have in
M
N
M
M
Σ
ag
at
k
NM
M
j=
m==1
and
N2
jjn
NM
Oim
S k.
==1
m=1
Hence, by the symmetry of and by the triangle inequality,
N
jj
M
Oim
2k.
1=1 m=
Now, since all entries of A. S, C, C. Q. and F are in [0, 1]. may use Lemmas E.3 and E.4 to derive approximation errors for the gradients L. Specifically, for any 0 < Pı < 1, for every k E [K] there is event Aş of probability at least P1 such that
log /P1) log(N) log
V V, (m)
S <4V
M
Moreover, for every E [K] and j E [D]. and every 0 < p2 < 1 there is an event Ck., probability at least 1 - P2 such that
VIL Sn. (m)
41
2 log(11/22) (1/p2) log(2)
D
M
For the approximation analysis of V 4m Lt note that the index is random, so we derive uniform convergence analysis for all possible values of nm- For that, for every E [N] and k E [K], define the vector
M
2
Nn. (m)
(Cn.y - On,n, CCknn,k
M2
1=1
D
2
(Cn,.n ) A
Σ (pr,d sn,d) fr.ds
M
MD
d=1
Note that V Vin. ((n) not a gradient of (m) (since n is not a sample from {nm} the gradient must be zero), but is denoted with V for its structural similarity to V 9ma (n), Let 0 < pa < 1. By
25

---

Lemma E.3 for every k E
[K] there is an event B3 of probability at least 1 Ps such that for every
[
M
log((1/))) + (N) + log(2)
V a
L
V Un.,k
L(n)
N
M
This means that in the event Bk, for every m E [M] we have
M
(m)
4 NV
2 llg(11/ps) + 2 log (N) 1-220 2lg((2)
9.m L
9mm
M
Lastly, given 0 < p < choosing Pi P3 = p/3K and P2 p/3K D and intersecting all events for all corrdinates gives and event & of probability at least p such that
2 2log(1/p)) + 2 (N) + log K) + (2g
s Vr L (rnL(m)
</1
M
41 D
2log + 2og K)
2 () + (2g
V Sha I. V Ie,
M
and
V Anmak
La
M V N
[(m)
4
2 log( 1/pa) + 2 log N) + 2 log K) + 2 log
9rmm
N
M
Additional experiments
F1 Node classification
Setup. We evaluate ICG-NN and ICG,-NN on the non-sparse graphs tolokers 443 squirrel 45 and twitch-ge twitch-gamers gamers [36]. We follow the 10 data splits of Platonov et al. [3] for tolokers, the 10 data splits of Pei et al. [2), Li et al. [34] for squirrel and the 5 data splits of Lim et al. (36), Li al. (34] for wiich-ggmmess We report the mean ROC AUC and standard deviation for tolokers and the accuracy and standard deviation for squirrel and twitch-gamers. We also evaluate the relative Frobenius error between the graph and the ICG as a measure of the quality of the ICG approximation.
The baselines MLP, GCN 30 GAT 53 GCG 66). GPR-GNN 14, LINKX [36,, GloGNN 34 taken from Platonov al. 43 for tolokers and from Li et al. 34 for squirrel, twitch-gamers
and penn94. We use the Adam optimizer and report all hyperparameters in Appendix !
Results. All results reported in Table 2 Observe that ICG-NNs achieve state-of-the-art results across the board, despite the low ratio of edge (graph densities of 2.41 10 4 to 8.02 10-3). ICG- NNs surpass the performance of more complex GNN models such as GT, LINKX and GloGNN, which solidify ICG-NNs as a strong method and a possible contender to message- neural networks.
F.2
Comparison with graph coarsening methods large graphs
In this section we highlight the main differences and similarities between graph coarsening methods and ICG-NNs, followed by empirical comparison over large graphs.
F.2.1 Conceptual comparison
graph condensation methods (26] and graph summarization methods [68] replace the original graph by one which has fewer nodes, with different features and different topological structure, while sometimes preserving certain properties, such as the degree distribution [68].
Graph coarsening methods [18 25
Theoretical guarantees. Graph coarsening methods do not typically stem from theoretical guarantees, whereas ICG-NNs provably approximate the graph.
Computational complexity. Graph coarsening methods usually account for the graph's 's structure by apply passage-passing the coarsened graph. Condensation methods require O(EM) operations
26

---

Table Results large graphs. Top three models are colored by First, Second, Third.
tolokers
squirrel
twitch-gamers
# nodes
11758
5201
14
# edges
519000
217073
6797557
avg. degree
88.28
41.71
40.43
relative Frob.
0.69
0.39
0.8
MLP
72.95 + 1.06
28.77 + 1,56
60.92 + 0.07
GCN
83.64 +: 0,67
53.43 +: 2.01
62.18 + 0.26
GAT
83.70 +: 0.47
40.72 +: 1.55
59.89 + 4.12
GT
83.23 +: 0.64
HGGCN
73.35 + 1.01
35.70 1.00
OOM 61.89 + 0.29
GPR-GNN
72.94 + 0.97
34.63 + 1.22
LINKX
61.81 + 1.80
66.06 = 0.19
GloGNN
73.39 + 1.17
57.88 + 1.76
66.34 + 0.29
ICG-NN
83.73 0.78
58.48 + 1.77
65.27 + 0.82
ICG.-NN
83.51 = 0.52
64.02 + 1.67
66.08 + 0.74
Table 3: Comparison with graph coarsening methods over large graphs. Top three models are colored by First, Second, Third.
Reddit
Flickr
# nodes
232965 11606919
89250
# edges
899756
avg. degree
49.82
10.08
Coarsening
47.4 0.9
44.6 0.1
Random
66.3 + 1.9
44.6 + 0.2
Herding
71.0 + 1.6
44.4 + 0.6
K-Center
58.5 + 2.1
44.1 + 0.4
One-Step
45.4 + 0.3
DC-Graph
90.5 + 1.2
45.8 + 0.1
GCOND
90.1 + 0.5
47.1 0.1
SEGC
89.9 + 0.4
47.1 + 0.1
GC-SNTK
46.6 0.2
ICG-NN
89.6 + 1.2
50.4 0.1
ICN,.NN
93.6 + 1.2
52.7 + 0.1
to construct a smaller graph 26 and M the number of nodes of the condensed graph. Conversely, ICGs estimate the ICG with O(K2N + KE) operations, where K is typically smaller than M.
67
56
where E is the number of edges of the original graph
Node processing. Graph coarsening methods process representations graph, while ICG-NN also process the fine node information at every layer.
iteratively coarsened
Graphs larger than memory. ICG-NNs offer subgraph sampling approach when the original graph cannot fit in memory. In contrast, the aforementioned methods lack a strategy for managing smaller data structures when computing the compressed graph.
F.2.2 Empirical comparison
Setup. We evaluate ICG-NN and ICG,,-NI on the large graph datasets Flickr (65] and Reddit 23 We follow the splits of [67 and report the accuracy and standard deviation.
The standard graph coarsening baselines Coarsening 25 Random 25 Herding 58
K-Center 48
One-Step [27] and the graph condensation baselines DC-Graph (66). GCOND 26 SFGC 67 and
GC-SNTK [56) are taken from [6].6)] We use the Adam optimizaer and report all hyperparameters
in Appendix [
Results. ICG-NNs present state-of-the-ar performance in Table when compared vareity of both graph coarsening methods and graph condensation methods, further solidifying its effectiveness.
27

---

84
ROC AUC
80
Accuracy
78
76
74-
ICG.NNN
45
ICG-NN
5
25
50
100
150
200
250
5
25
50
100
150
200
250
Number of communities
Number of communities
Figure 4: Test ROC AUC tolokers (Ieft) and test accuracy of squirrel (right) as a function of the number of communities.
F.3 Node classification large graphs using Subgraph SGD
the large graph Flickr [65]. We follow the splits of [67] and report the accuracy and standard deviation. We set the ratio of condensation
Setup. We evaluate ICG-NN and ICG,,-N
Table 4: Results Flickr using 1% node sampling. Top three models are colored by First, Second, Third.
M to 1%, where N and M are the number of nodes in the graph and the number of sampled nodes.
N
Model
Accuracy
Coarsening
44.6 0.1
The graph coarsening baselines Coarsening (25 Ran-
Random
4..6
dom [25] Herding [58]. K-Center (48), One-Step (27
Herding
44.4 0.6
and the graph condensation baselines DC-Graph [66].
K-Center
44.1
GCOND [26]. SFGC [67] and GC-SNTK [56] are taken
One-Step
45.4
from 67 56]. We the Adam optimizaer and report all
hyperparameters in Appendix
DC-Graph
45.8 0.1
GCOND
47.1 0.1
Results. Table shows that ICG,,NN with subgraph ICGm with % sampling rate, achieves competitive per- formance with coarsening and condensation methods that operate on the full graph in memory.
SFGC
47.1 + 0.1
GC-SNTK
46.5 + 0.2
ICG-NN ICG,,NN
50.4
50.8 0.1
F44 Ablation study over the number of communities
Setup. We evaluate ICG-NN and ICG,-NN non-sparse graphs tolokers 43 and squirrel 45
We follow the 10 data splits of Platonov et al. 43 for tolokers and Pei et al. 42 Li et al. [34] for squirrel. We report the the mean ROC AUC and standard deviation for tolokers and the accuracy and standard deviation for squirrel.
Results. Figure shows several key trends across both datasets. First, anticipated, when very small number of communities is used, the ICG fails to approximate the graph accurately, resulting in degraded performance. Second, the optimal performance is observed when using relatively small number of communities, specifically 25 for tolokers and 75 for squirrel. Lastly, using a large number of communities does not appear negatively impact performance.
F.5
The cut-norm and Frobenius norm
While the cut norm is the theoretical target the ICG approximation, it is expensive to estimate directly. However, Theorem implies that optimizing the Frobenius norm, which is computationally inexpensive, leads to a small cut norm.
In this experiment, we first aim to demonstrate the positive correlation between the Frobenius error and the cut norm error. Moreover, we show that even though the Frobenius error cannot be made close to zero in general, it is still correlated with cut norm. We show that when the relative Frobenius
28

---

0.025
0.25
Relative cut cut- nronnom
50
0.15
0.010
0.10
100
0.005
100
250
150
250
200
150
0.090
0.00
0.70
0.75
0.50
0.85
0.90
0.325 0.350 0.375 0.400 0.425 0.450 0.475 0.500 0.525 Relative frobenius norm
Relative frobenius
Figure Cut-norm as a function of Frobenius norm on the tolokers (left) and squireel (right) datasets. The number of communities used is indicated next to each point.
Table 5: Time until convergence in seconds on large graphs.
tolokers
squirrel
twitch-gamers gamers
# nodes # edges
11758
5201
168114
519000
217073
6797557
avg. degree
88.28
41.71
40.43
random init.
83.30 + 0.92
62.03 + 0.98
64.73 0.44
eigenvector init.
83.31 = 0.64
62.10 + 1.67
66.10 + 0.42
error is reduced below specified threshold (not close zero in general), the ICG approximation allows ICG-NNs to achieve tate-of-theeart results.
Setup. We evaluate ICG approximation non-sparse graphs tolokers 43 and squirrel 445 We vary the number of communities used by the approximation and report the relative cut-norm (estimated by (3) function of the relative Frobenius norm. We also present the resulting relative Frobenius error for our node classification experiments in Table 2
Results. As expected, the cut-norm and Frobenius norm are positively correlated, both decreasing as more communities are used, as shown in Figure We also observe Table ICG-NNs perform best on the squirrel dataset and worst twitch-games aligning with their relative Frobenius error. The lower the relative Frobenius error, the more accurate the ICG approximation, leading to better performance. Table 2 and Figure also revealed useful rule of thumb: when the relative Frobenius error is below 0.8, it correlates with very small cut norm error. This, in turn, leads to an accurate ICG approximation, enabling ICG-NNs to achieve state-of- of-the--rt results.
F.6 Initialization
We repeated the node classification experiments presented in Table using random initialization when optimizing the ICG, and compared the results those obtained with eigenvector initialization.
Setup. We evaluate ICG-NN and ICG,,NN on the non-sparse graphs tolokers 43 squirrel 45 and tiich--gmmrss
We follow the 10 data splits of Platonov al. 43 for tolokers. the 10 data splits of Pei et al. 42 Li et al. 34] for squirrel and the 5 data splits of Lim et al. (36), Li et al.
gamers 36
34 for witchh-gamers. We report the mean ROC AUC and standard deviation for tolokers and the accuracy and standard deviation for squirrel and twitch-gamers.
Results. Table indicates that cigenvector initialization generally outperforms random initialization across all datasets. While the improvements are minimal in some cases, such as with the tolokers and squirrel datasets, they are more pronounced in the twitch-gamers dataset.
Additionally, eigenvector initialization offers a practical advantage terms of training efficiency. On average, achieving the same loss value requires 5% more time when using random initialization
29

---

compared to eigenvector initialization. This efficiency gain further supports the utility of the proposed initialization method.
Run-time analysis
In this subsection, we compare the forward pass run times of our ICG approximation process, signal processing pipeline (ICG,-NN) and the GCN (30) architecture. We sample graphs of sizes up to 7,000 from dense and sparse Erdös- Rényi distribution ER (n, p(n) 0.5) and ER(n, p(n) )0), a
correspondingly. Node features are independently drawn from [0, 1] and the initial feature dimension is 128. -NN and GCN use hidden dimension of 128, layers and output dimension of 5.
ICG approx. time Ix10- sec]
ER(n. p(n) 50
ICG approx. time [x10-2 sec]
ER(n,p(n) 0.5)
80
10:
y- 0.0367x
1.4387
R²
60
40
K- 10: 0.3702
0.1477 23.1703
40
35
K- 100: R² 0.4876
1686x 35.7329
20
30
50
60
70
80
20
40
GCN time 10 4 sec]
GCN time [x10 sec]
Figure 6: Empirical runtimes: K-ICG approximation process as function of GCN forward pass duration on the dense (Ieft) and sparse (right) Prdös-Rény' distribution ER (n, p(n) 0.5) and 50 for K=10, 100.
ER(n, ((n)
Results. Figure 6 demonstrates a strong linear relationship between the runtime of our ICG approxi- mation and that of the message-passingg neural network GCN for both sparse and dense graphs. Unlike GCN, our ICG approximation is versatile for multiple tasks and requires minimal hyperparameter tuning, which reduces overall time complexity. Additionally, Appendix F7 reveals a strong square root relationship between the runtime of ICG,-NN and the runtime of GCN for both sparse and dense graphs. This aligns with our expectations, as the time complexity GCN O(E), while the time complexity of ICG-NNs is ONN), highlighting the computational advantage of using ICGs over message-passing neural networks.
F88 Time until convergence
Setup. We measured the average time until convergence in seconds for the GCN and ICG,,NN architectures on the non-sparse graphs tolokers 4 squirrel
45)
and twitch-gamers (36] We follow
ER(n, ER(n,p(n) )0)
ER(n, 0.5)
[CG,-NN time Ix10-4 sec]
ICG,-NN CNN-NN NN time xx0-> sec]
24
22
20
K 10: R 0.9635
K 10: 0.9666
y 3.5212/x 66514
0.49814x 0.177
18
100. 93506
0.9177
16
y 3.1491/7 -10678
y 0.4836/xx
60
70
80
GCN time [x10 sec]
GCN time [x10-2 sec]
Figure 7: Empirical runtimes: K-ICG, as function of GCN forward pass duration on the dense (left) and sparse (right) Erdös-Rénn Rényi distribution (R(n,p(n) 0.5) and ER(n, p(n) 50 for
K=10, 100.
30

---

Table 6: Time until convergence in seconds on large graphs.
tolokers
squirrel
twitch-gamers
GCN
510
3790
1220
ING,
33
225
49
the 10 data splits of Platonov al. 43 for tolokers, the 10 data splits of Pei al. [4]]. et al. [34] for squirrel and the data splits of Lim et al. [36]. Li et al. [4] for twitch- gamers. We ended the training after 50 epochs in which the validation metric did not improve. We set the pypae-eassmeters with best validation results.
Results. Table [6] shows that ICG,-NN consistently converges faster than GCN across all three benchmarks. Specifically, converges approximately 15 times faster on the tolokers dataset, 17 times faster on the squirrel dataset, and 25 times faster on the twitch-gamers dataset compared to GCN, indicating a significant improvement efficiency.
F.9 Memory allocation analysis
In this subsection, we compare the memory allocated during the ICG approximation process and during forward pass of the GCN (30 architecture. We sample graphs of sizes up 2,000 from dense Erdös-Rényí distribution ER(n, p(n) = 0.5). Node features are independently drawn from (0, 1] and the initial feature dimension is 128. ICG,,NN -NN and GCN use hidden dimension of 128, 3 layers and an output dimension of 5.
2250
K=10 (y=0.078x + 1.337, R2
ICG approximation [MB]
2000
100 (y=0.808x 7.147, =
1750
1500
1250
1000
750
500
250
0
500
1000
1500
2000
GCN [MB]
Figure 8: Memory allocated for K-ICG approximation (K=10,100) as function of the memory allocated for GCN on graphs G ER(n,p(n) 0.5).
Results. Appendix F9 demonstrates strong linear relationship between the the memory allocated during the ICG approximation process and during a forward pass of the message-passing neural network GCN. This aligns with our expectations: the memory allocation for the GCN architecture is OEED), and of ICG-NNs O(EK + NKD), where D is the feature dimension and K the number of communities used for the ICG approximation.
31

---

G Additional related work
Latent graph GNNs.
One way interpret ICG-NNs are as latent graph methods, where the ICG approximation of the given graph G is seen as a latent low complexity "clean version" of the observed graph G.
In latent graph methods, the graph on which the GNN is applied is inferred from the given data graph, non-graph data. Two motivations for latent graph methods are (1) the given graph noisy, and the latent graph is its denoised version, or (2) even if the given graph is "accurate", the inferred graph improves the efficiency of message passing. Our ICG GNN can be cast in category (2), since we use the latent ICG model to define an efficient "message passing" scheme, which has linear run-time with respect to the number of nodes.
from
Some examples of latent graph methods are papers like 31 57 graph from non-graph data. Papers like (39 59 28
which learn a latent treat the given graph noisy partially
21
observed, and learn the "clean" graph. Papers like [54, 50) modify the given graph to improve the
efficiency of message passing (c.g.. based on the notion of oversquashing [5),, and 41 modifies the
weights of the given graph if the nodes were sampled non-uniformly from some latent geometric graph. Additionaly, attention based GNN methods, which dynamically choose edge weights [53] 55 can be interpreted as latent graph approaches.
H
Dataset statisties
The statistics of the real-world node-clasiification, spatio-temporal and graph coarsening benchmarks used can be found in Tables 7 9
Table 7: Statistics of the node classification benchmarks.
tolokers
squirrel twitch-gamers
# nodes (N)
11758
5201
168 1 14
# edges (E) avg. degree (
519000
217073
6797557
88.28
41.71
40.32
# node features
10
2089
7
# classes
5
metries
AUC-ROC
ACC
ACC
Table 8: Statistics of the spatio-temporal benchmarks.
METR-LA PEMS-BAY
nodes (N)
207
325
# edges (E)
1515
2369
avg. degree ( (
7.32
7.29
node features
34272
52128
Table 9: Statistics for graph coarsening benchmarks.
Reddit
Flickr
# nodes (N)
232965
89250
# edges (E)
114615892
899756
avg. degree
491.99
10.08
# node features
602
500
# classes
41
7
32

---

I Hyperparameters
In Tables 10 to 12
we report the parameerssessess used in our real-world node-classification, spatio-
temporal and graph coarsening benchmarks.
Table 10: Hyper-parameters used for the node classification benchmarks.
tolokers
squirrel
twitch-gamers
# communities Encoded dim
25
75
50
128
À
Approx. Ir Approx. epochs
0.01, 0.05 10000
0.01, 0.05
0.01, 0.05
10000
10000
# layers
3,4,5
3,4,5
3,4,5,6
hidden dim
32, 64
64, 128
64, 128
dropout
0, 0.2
0, 0.2
0, 0.2 V
residual connection
Fit
0.001, 0.003, 0.005 0,001, 0.003, 0.005 0.001, 0.003, 0.005 3000
Fit epochs
3000
3000
Table 11: paaaeeeassmeters used for the spatio-temporal benchmarks.
METR-LA
SEMS-BAY
# communities Encoded dim
50
100
À
0
Approx. Ir Approx. epochs
0.01, 0.05, 0.1 0.01, 0.05, 0.1 10000
10000
# layers hidden dim
3,4,5
3,4.5,
32, 64, 128 0.001, 0.003 300
32, 64, 128
Fit Ir
0.001, 0.003 300
Fit epochs
Table 12: Hyper-parameters used for graph coarsening benchmarks.
Reddit
Flickr
communities
50, 600
500
Encoded dim
0
0,1 0.01, 0.05
Approx. Ir
0.05
Approx. epochs
10000
10000
# layers hidden dim dropout
2,
4
128, 256
128, 256
0, 0.2 /
0
residual connection
Fit Ir
0.005, 0.01 3000
0.001, 0.003, 0.005
Fit epochs
1500
For spatio-temporal dataset, we follow the methodology described in [5]] where the time of the day and the one-hot encoding of the day of the week are used as additional features.
33

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). ). general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We prove our proposed constructive version of the Weak Graph Regularity Lemma. We use the construction to then develop new pipeline for learning on large non-sparse graphs efficiently, following what is written in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
34

---

Justification: We discuss the model's limitations in the conclusions section. Primarily, our approach is constrained the relatively large. undirected graph setting. Consequently, this restricts the number of datasets we can experiment on and, by extension, limits the scope of our experimental analysis.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The appendix contains the complete proof's for all of our theoretical results, along with the full set of assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
35

---

The main paper details the models, datasets, data splits, and optimizer used. Additionally, the appendix includes the complete hyperparameter grids tested for each experiment and any other relevant implementation details.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g.. a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide a URL to our reproducible repository, which includes detailed operation instructions. Additionally, the appendix contains the complete hyperparameter grids tested for each experiment and any other relevant implementation details.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips http:///www....eeeeee//////ssssa
for more details.
36

---

The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
reproducible, they
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We follow the standard train and test splits and optimizer. The train/test splits and optimizer detailed in Section 6 and present in repository. The appendix contains the complete hyperparameter grids tested for each experiment and any other relevant implementation details.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We include standard deviation error bars in our figures and tables.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
37

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We use a single NVidia L40 GPU (with standard memory and time of execution) in all of our experiments. This is reported in the paper.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
The paper proposes a general purpose computational pipeline for efficient learning on large non-sparse graphs, focusing mainly on theoretical/maahheatiee results, e.g., a new constructive version of the Weak Graph Regularity Lemma,. We believe there are no societal consequences of our work that require specific highlighting here.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinfornation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
38

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not pose such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite the owners of each dataset and state the version and splits that are used in Section
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwppsai thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- e-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
39

---

Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
40


Reviews:
[{"review_id": "pUyWGQNh0Z", "reviewer": "Reviewer_Z1J6", "summary": "The main idea of this paper is to break a graph into communities and approximate the graph with a limited number of these communities. The main idea of the work is rooted in the cut metric, which is defined for signals on the graphs and includes both graph structure and node features. They approximate the cut metric with a Frobenius norm version of the problem and prove a constructive version of the Weak Regularity lemma. Their reformulation allows the problem to be solved with a gradient descent algorithm. They also provide a version of subgraph gradient descent for larger graphs. They also theoretically analyze the approximation power of their subgraph gradient descent for finding the gradient on the whole graph. They introduce two models to be used after finding the communities and signals for these communities. The first model uses a Transformer architecture on the community signals, but the second one learns the community signals along the layers of their network. They provide time analysis on their work using random Erdős-Rényi graphs and show that their method is much more efficient than Graph Convolutional Network (GCN) in a forward pass of their model (used after finding the communities). They also get competitive results on node classification tasks for a few datasets and apply their work for a spatio-temporal task for traffic forecasting.", "questions": "1. Is there any time measured for fitting an ICG for a graph with the gradient descent? It seems to be at least as complex as learning the main task. However, I admit that it has the advantage of requiring no hyperparameter tuning and can be done once, with the condition that it can be done on large graphs with a reasonable calculation budget.\n\n2. What is the relation of your work to graph coarsening methods? Methods such as DiffPool [1] seem to be learning a similar thing as a layer in the neural network, and thus their pooling is task-dependent. What are the advantages of your method over these techniques?\n\n[1] Ying, Zhitao, et al. \"Hierarchical graph representation learning with differentiable pooling.\" Advances in neural information processing systems 31 (2018).", "limitations": "The method seems to be more efficient for very dense graphs, which is discussed to some extent in the paper. However, there also seem to be some mistakes in their argument (discussed in the Weaknesses section).", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper has deep roots in the theory and does not neglect to provide theoretical analysis for any decision made in their process.\n\n2. I am not an expert in the domain of signal processing for graphs, and I do not know to what extent the proofs in this paper are novel. However, they seem to present interesting results, and introducing them to the modern graph learning community is valuable in itself.\n\n3. Their initial algorithm for finding the communities does not appear to be any simpler than learning on the graph by a Message Passing Neural Network (MPNN). However, it has the advantage of not requiring any hyperparameter tuning and only needing to be done once. \n\n4. They have done a good job of finding spatiotemporal tasks where the graph structure is fixed, but the signals are changing. The initial community finding process load can be better justified in this setup.", "weaknesses": "1. Their analysis on the time complexity and efficiency of their method seems to be incorrect. Namely, in line 257, they mention that the message passing networks need $O(ED^2)$ operations. This is not correct. Message passing networks usually have a node-level processing which is $O(ND^2)$ and then a message aggregation process which is $O(ED)$, as there is no matrix multiplication along the edges and it is just adding the vectors of size D. Thus, the total complexity is $O(ND^2 + ED)$. \nThis is a significant problem as they mention their method is efficient if $K = O(Dd)$, where $D$ is the size of the features and $d$ is the average degree of the graph. By correct complexity of the message passing networks, we can see that their method only works comparably efficiently if $K = O(d)$, which is very small for most of the graphs. While Figure 2 suggests that their method is much faster than the GCN, the reason is that the graphs they sample are very dense, with $d = O(N)$ and $E = O(N^2)$. This is evident from Figure 6 in their appendix, where they use a more sparse graph with $d = 50$. We can see that when $K=100$, the time required by their method is similar to that of the GCN.\n\n2. The paper gets unnecessarily complex and hard to understand, especially with the notations, which are excessive and sometimes inconsistent. For example, starting from Definition 2.1. the definition of the matrix norm is just used for the adjacency matrix A and feature matrix S in this paper, defining new matrices B and Z here just makes it confusing. At any point, if you require to define a formula that is general on all matrices, like when you describe the Frobenius norm, you can use names like X which does not feel to be a special matrix that might next definitions depend on it. \n\n     Starting in Section 3.1, the use of C and P for finding the ICG on (A, S) using b vectors, and continuing with F at another point, makes it very confusing. One reason for this can be that B seems to be defined earlier in Definition 2.1, but it is not really connected to the b vectors used here.\n\n      Definition 3.1 defines $\\mathcal{Q}$ as a set of functions. However, starting with Definition 3.2, it uses the term \"soft affiliation model\" for $\\mathcal{Q}$. I am not sure what is meant by \"model\" here and whether we are still referring to the same $\\mathcal{Q}$. This is particularly confusing because, as I understand it, each member of $\\mathcal{Q}$ is a function from $[N]$ to $\\mathbb{R}$. Therefore, $\\mathcal{Q}$ is a subset of $\\mathbb{R}^N$, and the space defined for $[\\mathcal{Q}]$ in Definition 3.2 is not clear to me.\n\n3. While the main point is the efficiency of the method, the results for node classification are very limited, both in the number of datasets and the size of the datasets, and do not quite reflect the effectiveness of the method.\n\n4. Their theory (Theorem 3.1) only works for very large K values for reasonably sparse graphs that can be seen in most datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> W1: Their analysis on the time complexity…\n\n>L1: The method seems to be more efficient for very dense graphs…\n\n**Answer:** A general message passing layer applies a function on the concatenated pair of node features of each edge. We refer to this general formulation of MPNN, which takes $O(ED^2)$ operations for MLP message functions. \n\nThe reviewer is correct that in some simplified message passing layers (e.g., GCN and GIN) the message is computed using just the feature of the transmitting node. Here, the complexity is reduced to $O(ED+ND^2)$. We will add this special case to the paper and compare asymptotics to ICGNN.\n\nEven for such simplified GNNs, for graphs with large average degree (the graphs of interest in our paper), taking $K$ less than $d$ makes sense. While standard benchmarks of large graphs are quite sparse (**tolokers**, $d=88$, **squirrel** $40$, **reddit** $50$), we believe that this is a result of the research community focusing on sparse graphs when developing methods for large graphs. However, in industrial applications, one often has to work with large and not very sparse graphs. See examples under **Choice of datasets** in the common response. For lack of such large and relatively dense publically available graphs, we have to make do with the available sparse large graphs, where our method performs remarkably well nevertheless. We hope the reviewer would agree that the lack of available high quality benchmarks should not be a reason to reject our contribution.\n\nLastly, while taking $K=d$ may seem to give the same efficiency for GCN and ICG-NN, an ICG-NN has the advantage that it works with a regular array of a fixed dimens as the data structure. In contrast, GCN has to move between two data structures - the list of edges and the list of node features. This is less efficient in practice. \n\n> W2: The paper gets unnecessarily complex…\n\n> Starting in Section 3.1, the use of $C$ and $P$ for finding…\n\n**Answer:** We are happy to improve our notations in the revised paper.\n\nThe matrix norms in our paper are not used on (non-negative) adjacency matrices but on (real-valued) differences between adjacency matrices. The distinction is critical. The cut norm of an adjacency matrix is just its L1 norm, but the cut norm of a general matrix is not. Thus, using the adjacency matrix $A$ to denote the variable inside the cut norm would be an abuse of notation. We will clarify this in the revised paper.\n\nWe cannot replace the notation $P$ by $F$, since they are related by $P=QF$. We will change $b$ in (5) to $f$ to be consistent with the relation between $P$ and $F$. We will also change the generic matrix notation in Definition 2.1 to $M$.\n\n> Definition 3.1 defines $\\mathcal{Q}$ as a set of functions...\n\n**Answer:** Definition 3.1. introduces rigorously the *soft affiliation model* $\\mathcal{Q}$, which is a set of functions $q:[N] \\rightarrow \\mathbb{R}$. Given a soft affiliation model $\\mathcal{Q}$, Definition 3.2. rigorously introduces *the soft rank-1 intersecting community graph model* $[\\mathcal{Q}]$.\n\nWe are happy for the opportunity to improve the wording and make the definition clearer. We will start Definition 3.2 with:\n\n\"Let $d\\in\\mathbb{N}$, and let $\\mathcal{Q}$ be a soft affiliation model. We define $[\\mathcal{Q}]\\subset\\mathbb{R}^{N\\times N}\\times \\mathbb{R}^{N\\times D}$ to be the set of all elements...\"\n\n> W3: While the main point is the efficiency of the method, the results for node classification...\n\n**Answer:** We conducted additional experiments using the **flickr** dataset, which is significantly larger than the datasets used in our initial submission. Our IGCNN with subgraph ICGm with 1% sampling rate, achieves competitive performance with competing methods that operate on the full graph.\n\n| Random          | DC-Graph        | GCOND           | SFGC            | GC-SNTK         | $\\text{Sub-ICG}_u-\\text{NN}$          |\n|------------------|-----------------|-----------------|-----------------|-----------------|----------------|\n| 44.6 ± 0.2       | 45.8 ± 0.1      | 47.1 ± 0.1      | 47.1 ± 0.1      | 46.6 ± 0.2      | **50.8** ± 0.1     |\n\n> W4: Their theory (Theorem 3.1) only works for very large K…\n\n**Answer:** We managed to significantly improve the asymptotics, which requires only a minor revision to the proof. **The multiplicative constant in (6) is now $3N/2\\sqrt{E}$ instead of $3N^2/2E$**. Moreover, we show that this asymptotic is essentially tight.  Now, ICG requires $K>N^2/E$ to guarantee that ICG approximates any given graph. See **Improved asymptotic analysis** under the common response for more details.\n\nOn the other hand, as written in the paragraph in Line 173, in practice, ICGs approximate also sparse graphs well. In the spare case the theory *only motivates* a class of graphs on which the computational method works, but does not guarantee a quantitative bound. This approach to motivating computational methods from theory is very common and accepted by the research community.\n\n> Q1: Is there any time measured for fitting an ICG…\n\n**Answer:** Run time analysis which shows a linear relationship between the runtime of ICG approximation and GCN be found in **Appendix F.4**, lines 1191-1194. The reduction in hyperparameter tuning is mentioned to motivate the usage of ICGs instead of MPNNs in **Section 8**, lines 381-382. We will highlight these points further in the final version. \n\n> Q2: What is the relation of your work to graph coarsening...\n\n**Answer:** In **Comparison of ICG-NN to graph coarsening** in the common response, we highlight the main differences. The summary is:\n1. Coarsening methods do not have theoretical guarantees. ICGs provably approximate the graph.\n2. Pooling methods do not asymptotically improve run-time. ICG-NNs do.\n3. Pooling methods are MPNNs. ICG-NN is not interpreted as message passing.\n4. Graph coarsening process representations on an iteratively coarsened graph. ICG-NNs process the fine information at every layer.", "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": "BYLXusdWva", "reviewer": "Reviewer_2roR", "summary": "This paper proposes the Intersecting Communities Graph (ICG), which enables efficient learning on very large non-sparse graphs by representing the graph as a linear combination of intersecting communities such as cliques. Unlike Message Passing Neural Networks (MPNNs), the proposed method operates with memory complexity proportional to the number of nodes, even for extremely large graphs. Although constructing the ICG takes linear time, this is an offline preprocessing step that is performed only once, and subsequent learning tasks are conducted very efficiently. The effectiveness of the proposed method is empirically demonstrated using both synthetic and real-world data.", "questions": "- Is there a straightforward way to determine how dense a graph needs to be for the proposed method to be effective, or under what conditions of sparsity it remains effective? Are these the conditions mentioned in lines 169-172? To what extent are these criteria met in each dataset in the experimental section?", "limitations": "If there is no simple way to determine the applicability of the proposed method, it may limit the range of its practical application.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- This paper is clearly and systematically written, effectively utilizing figures and equations to concisely present the entire logical development of the paper.\n- The methodology introduced with the Intersecting Communities Graph (ICG) offers a novel approach that is different from traditional graph machine learning methods. It provides a new pipeline that enables learning on large and dense graphs.\n- By leveraging the Weak Graph Regularity Lemma, the paper provides a theoretically rigorous and efficient method for constructing ICG.\n- The validity of the experimental results demonstrates the effectiveness of the proposed method.", "weaknesses": "- The proposed method has been shown to dramatically accelerate the learning of dense large-scale graphs. However, it is necessary to have a straightforward way to determine how dense a graph needs to be for the proposed method to be effective, or under what conditions of sparsity it remains effective. It seems that the conditions mentioned in lines 169-172, such as $K > N^4/E^2$, $K < d$, $E > N^{5/3}$, and $d > N^{2/3}$, might serve this purpose. However, these conditions are derived based on the Weak Regularity Lemma, and it is not clearly stated whether they can be used as practical criteria for the above judgments. Furthermore, in the experimental section, these indicators for each dataset do not appear to be clearly presented, making it difficult for readers to understand the existence of such effective criteria. By clearly demonstrating such criteria, the applicability of the proposed method could potentially be broadened.\n- There are a few minor mistakes. For example, could (14) on line 110 be a mistake for (4)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and for highlighting the novelty of our approach and the overall quality of the paper. We address each of their questions/concerns below.\n\n> W1: …it is necessary to have a straightforward way to determine how dense a graph needs to be for the proposed method to be effective, or under what conditions of sparsity it remains effective…\n\n> Q1: Is there a straightforward way to determine how dense a graph needs to be for the proposed method to be effective…\n\n> L1: If there is no simple way to determine the applicability of the proposed method, it may limit the range of its practical application.\n\n**Answer:** We first note that after submitting the paper, we managed to significantly improve the asymptotics, which requires only a minor revision to the proof. **The multiplicative constunt in (6) is now $3N/2\\sqrt{E}$ instead of $3N^2/2E$**. Moreover, we show that this asymptotic is essentially tight. Namely, there are graphs for which there does not exist any ICG that approximates them with an error less than $O(N/\\sqrt{KE})$. This can be read from Theorem 1.2 in [1] (when converting their result to our definitions and notations). While this response is too short to show the proof, we are happy to send an anonymous PDF with the proof to the AC according to the rules and regulations of NerIPS, so you can verify it.   This improved theorem leads to a better comparison to MPNN methods. Now, ICG requires $K>N^2/E$ to guarantee that ICG approximates any given graph. For example, for a graph with $10^5$ nodes and average node degree $800$, one needs $K=125$ communities.\n\nThis bound is still pessimistic for sparse graphs. As written in the paragraph in Line 173, we note that in practice, ICGs approximate also sparse graphs well under relevant structural assumptions. In the spare case where $K<N^2/E$, the theory only motivates the engineering, but does not guarantee a quantitive approximation bound for all lgraphs. In this case, we will write the following rule of thumb in the revised paper, which we actually observed and used in practice:\n\n\"We observe in practice that when the relative Frobenius error between the graph and the ICG is less than 0.8, the cut norm error is usually small.\" \n\nNote that the Frobenius error is cheap to compute, and it is computed anyway as part of the optimization, while the cut norm, which is the actual theoretical target, is expensive to estimate.\n\nWe will add this certificate to all of the tables in the paper.\n\n| METR-LA | PEMS-BAY | tolokers | squirrel | twitch-gamers |\n|---------|----------|----------|----------|---------------|\n| 0.44    | 0 .34    | 0.69     | 0.39     | 0 .8          |\n\n> W2: There are a few minor mistakes. For example, could (14) on line 110 be a mistake for (4)?\n\n**Answer:** Thank you for pointing that out. We will correct this error, along with any other minor typos.\n\n[1] Alon et al. Approximating sparse binary matrices in the cut-norm. Linear Algebra and its Applications, 2015.", "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": "GyhE99fFgQ", "reviewer": "Reviewer_hec5", "summary": "The paper proposes a novel method to improve the GNN efficiency for large and dense graphs by approximating them as Intersecting Community Graphs (ICGs). This approach significantly reduces time and memory complexity depending on the number of nodes rather than edges. The authors theoretically show the approximation of ICGs using the weak graph regularity lemma. Experiments demonstrate ICG’s efficiency in node classification and spatio-temporal data tasks.", "questions": "- p249: Why does the operation on Community feature vector F is O(K^2D^2) rather than O(KD^2)? F is a matrix, the shape of which is K x D, then MLP on this matrix will be computed in O(KD^2) like p252.\n- p253: Why is Q^{†}Q an identity matrix? Are the rows of Q linearly independent? I could not find the constraint or assumption on this. \n- Notations: How about using more distinguishable notations for node features S and signals \\italic{S}? This might not be clear to readers.", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The authors propose an efficient method to train large (and dense) graphs. The method is theoretically well-motivated and concretely proved with detailed explanations. The theory is interesting, and the techniques used can be applied to future work in various ways. In addition, there are diverse types of benchmarks and evaluations (runtime analysis, node classification, spatio-temporal graphs), and the paper presents their results clearly.", "weaknesses": "- From my perspective, ICG+GNN is similar to summarizing the graph into smaller units (e.g., coarsened nodes, communities, or subgraphs) and then performing message-passing between them. It is essential to acknowledge the line of research on GNNs with graph coarsening, summarization, and condensation. These methods have addressed the challenges in graph learning, especially for efficiency and scalability. The examples of recent papers are stated below, and some of the work should be compared with empirical experiments.\n  - Hierarchical Inter-Message Passing for Learning on Molecular Graphs (ICML workshop 2020)\n  - Scaling Up Graph Neural Networks Via Graph Coarsening (KDD 2021)\n  - GRAPH CONDENSATION FOR GRAPH NEURAL NETWORKS (ICLR 2022)\n  - A Provable Framework of Learning Graph Embeddings via Summarization (AAAI 2023)\n  - Gapformer: Graph transformer with graph pooling for node classification (IJCAI 2023)\n  - Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data (NeurIPS 2023)\n  - Fast Graph Condensation with Structure-based Neural Tangent Kernel (WWW 2024)\n  - Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning (ICML 2024)\n- The time and memory required for real runtime to fit ICGs are not demonstrated. It makes sense that we only need to create the ICG once, but how much time and GPU memory does it take to create it?\n- Evaluation across datasets should be encouraged. Although various evaluations have been performed, a set of datasets was picked for each evaluation. A natural question arises as to whether this method robustly works across datasets.\n- Scalability should be validated by experiments on larger datasets and be compared with other efficient GNNs. The authors stated that constraints (single, large, undirected) restrict the number of datasets the authors can experiment on. But as far as I know, there are many more single, large, undirected graph datasets. Is the largest dataset used in the experiment large enough compared to existing efficient GNN research? Plus, is this method superior to existing scalable GNNs (e.g., sampling, coarsening) in practice (i.e., total training time)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and for finding our work theoretically significant.\n\n> W1: ICG+GNN is similar to summarizin…\n\n**Answer:** In **Comparison of ICG-NN to graph coarsening** in the common response, we highlight the main differences to pooling methods.\n\n> … The examples of recent papers are stated below…\n\n**Answer:** We agree, and for that reason we mentioned intersecting communities, stochastic block models and GNNs with local pooling in our related work sections: **Section 7** and **Appendix I**.\n\nLet us highlight the fundamental differences between the mentioned papers and ours:\n1. **Computational complexity** - Condensation methods require $O(EM)$ operations to construct a smaller graph [3,6,7,8], where $E$ is the number of edges of the original graph and $M$ is the number of nodes of the condensed graph. Conversely, we estimate the ICG with $O(E)$ operations.\n2. **Graph construction** - Methods like coarsening [1,2], condensation [3] and summarization [4], typically rely on heuristics. In contrast, ICGs provide a provable approximation of the original graph.\n3. **Handling graphs that do not fit in memory** - ICG-NNs offer a subgraph sampling approach when the original graph cannot fit in memory. In contrast, the aforementioned methods lack a strategy for managing smaller data structures when computing the compressed graph.\n\nIn line with the reviewer's suggestion, we will include the proposed references with an appropriate discussion.\n\nIn addition, we provide an empirical comparison in **Table 1** of **rebuttal.pdf** between our method and the aforementioned approaches on the **reddit** and **flickr** datasets. ICG-NNs achieve state-of-the-art performance.\n\n> W2: The time and memory required for real runtime to fit ICGs…\n\n**Answer:** In Appendix F.4 we compare the forward pass run times of our ICG approximation process, signal processing pipeline ($\\text{ICG}_u-\\text{NN}$) and the GCN architecture, demonstrating a linear relationship between the two. \n\nFollowing your request, we estimated the GPU memory used while fitting an ICG. We follow a similar setup to the run time experiments, with Erdos-Rényi graphs with 128-dimensional node features sampled from $U[0,1]$. Both $\\text{ICG}_u-\\text{NN}$ and GCN use a hidden dimension of 128, 3 layers and an output dimension of 5:\n\n**Figure 1** in **rebuttal.pdf** reveals a linear relationship between the memory allocated for $\\text{ICG}_u-\\text{NN}$ and for GCN. This aligns with our expectations: the memory complexity of GCN is $O(Ed)$, and of ICG-NNs $O(EK)$.\n\n> W3: Evaluation across datasets... \n\n> W4: …there are many more single, large, undirected graph... \n\n> Is the largest dataset used in the experiment large enough… \n\n**Answer:** We conducted additional experiments using the **reddit** and **flickr** datasets, which are significantly larger than the datasets used in our initial submission. We provide an empirical comparison in **Table 1** of **rebuttal.pdf** between our method and existing efficient approaches. ICG-NNs achieve state-of-the-art performance, further solidifying its effectiveness.\n\nOur method is designed for large and non-sparse graphs. Unfortunately, very few datasets meet this criterion. Standard benchmarks of large graphs are quite sparse. However, in applications in the industry, one often has to work with large and not very sparse graphs. Remarkably, ICG-NN still performs very well on the available sparse large graphs. In the paragraph in line 173, we explain how ICGs are still often meaningful for sparse graphs in practice. See **Choice of datasets** in the common response for more details.\n\n> Plus, is this method superior to existing scalable GNNs…\n\n**Answer:** We measured the time until convergence for the GCN and $\\text{ICG}_u-\\text{NN}$ architectures and tasks presented in **Appendix F.1, Table 2**. We ended the training after 50 epochs in which the validation metric didn’t improve. We set the hyper-parameters with best validation results. The results:\n\n|       | tolokers | squirrel | twitch-gamers |\n|-------|----------|----------|---------------|\n| GCN   | 510      | 3790     | 1220          |\n| ICGNN | 33       | 225      | 49            |\n\n$\\text{ICG}_u-\\text{NN}$ consistently converges faster than GCN across all three benchmarks. We will add this to the revised paper.\n\n> Q1: p 249: Why does the operation on Community feature vector $F$ is $O\\left(K^2D^2\\right)$...\n\n**Answer:**  When defining the general MLP, $F$ is flattened into a $KD$ dimensional vector. A linear operator hence requires $KD \\times KD$ parameters. We will clarify this in the text.\n\n> Q2: $p$ 253: Why is $Q^\\dagger Q$ an identity…\n\n**Answer:** If $Q$ is full rank at initialization (which is true almost surely for random initialization), and if $A$ is not low rank, then the optimal configuration of $Q$ is full rank. The optimization would not benefit from having multiple instances of the same community. This would be equivalent to reducing the number of communities from $K$ to $K-1$. We will clarify this in the paper.\n\n> Q3: How about using more distinguishable notations...\n\n**Answer:** We follow the standard numerical linear algebra notation, where $\\mathbf{s}_i$ denotes the i-th row/column of the matrix $\\mathbf{S}$ and it is standard to use the same letter for both.\n\n[1] Hierarchical Inter-Message Passing for Learning on Molecular Graphs, 2020.\\\n[2] Scaling Up Graph Neural Networks Via Graph Coarsening, 2021.\\\n[3] Graph Condensation for Graph Neural Networks, 2022.\\\n[4] A Provable Framework of Learning Graph Embeddings via Summarization, 2023.\\\n[5] Gapformer: Graph Transformer with Graph Pooling for Node Classifcation, 2023.\\\n[6] Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data, 2023.\\\n[7] Fast Graph Condensation with Structure-based Neural Tangent Kernel, 2024.\\\n[8] Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning, 2024.", "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": "55latDSRjL", "reviewer": "Reviewer_XnC3", "summary": "This paper introduces a novel approach for graph machine learning on large graphs using a concept called Intersecting Community Graphs (ICG). Traditional MPNNs face memory and computational challenges when dealing with large graphs due to their reliance on graph edges. The proposed method approximates the input graph as a combination of ICG, which requires fewer communities than the size of the graph. The ICG approach leverages a new constructive version of the Weak Graph Regularity Lemma to construct these approximations efficiently. The resultant learning algorithm operates with memory and time complexity linear to the number of nodes, rather than edges, making it suitable for very large, non-sparse graphs. Empirical evaluations demonstrate the method's applicability to tasks like node classification and spatio-temporal data processing.", "questions": "Has the author evaluated the relationship between the model's performance and the cut-metric between the approximated graph and the original graph? While I agree that in certain situations, such as social networks, ICG can approximate the original graph well, it is important to question whether this assumption holds in other contexts, such as molecular graphs.", "limitations": "N/A.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. In theory, the approach scales linearly with the number of nodes, addressing the memory complexity issues that plague traditional MPNNs when applied to large graphs.\n\n2. The paper introduces a constructive version of the Weak Graph Regularity Lemma, which could be of independent interest in graph theory and its applications.\n\n3. The method has been empirically validated on real-world tasks, showing competitive performance against existing models in node classification and spatio-temporal graph tasks.", "weaknesses": "1. The proposed method's speed advantage over MPNNs hinges on the assumption that the chosen number of communities K should be less than the node degree (line 170). However, real-world experiments sometimes require a K value larger than the node degree. For example, in the twitch-gamers dataset, K is set to 500 while the average node degree is 40.32. This discrepancy raises concerns about the practical speed benefits of the proposed method on real-world benchmarks.\n\n2. The computation of the ICG requires an offline pre-computation step that, while only performed once, involves a time complexity linear to the number of edges.\n\n3. In the Runtime Analysis section, the authors should also include a time comparison for the model's convergence, in addition to the per-epoch runtime.\n\n\n4. To demonstrate the efficacy of the proposed initialization method, the paper should include a comparison with existing initialization methods, such as random initialization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and for acknowledging the theoretical significance of our constructive version of the Weak Graph Regularity Lemma. We address each of their questions/concerns below.\n\n> W1: The proposed method's speed advantage over MPNNs hinges on the assumption that the chosen number of communities K should be less than the node degree (line 170)...\n\n**Answer:** Thanks for raising this point, this was an oversight. We conducted further experiments with a significantly lower number of communities $K=50$, achieving an accuracy of 66.08 ± 0.74 and 65.27 ± 0.82 for $\\text{ICG}_u-\\text{NN}$ and ICG-NN, correspondingly. Thus achieving state-of-the-art results while retaining the speed benefits of ICG-NN. \n\n> W2: The computation of the ICG requires an offline pre-computation step that, while only performed once, involves a time complexity linear to the number of edges.\n\n**Answer:** That is accurate. The time complexity of the ICG fitting process is similar to the time complexity of MPNNs, linear in the number of edges. Let us clarify that this is a strength of ICG-NNs. The ICG fitting process is only done once and does not require extensive hyperparameter optimization and architecture tuning, unlike MPNNS. Thus, ICG-NN offer a potentially significant advantage over standard MPNNs. This gap between ICG-NNs and MPNNs is further amplified for time series on graphs.\n\n> W3: In the Runtime Analysis section, the authors should also include a time comparison for the model's convergence, in addition to the per-epoch runtime.\n\n**Answer:** Based on the reviewers' suggestion, we measured the time (in seconds) until convergence for the GCN and $\\text{ICG}_u-\\text{NN}$ architectures across the node-classification tasks presented in **Appendix F.1, Table 2**. We ended the training after 50 epochs in which the validation metric didn’t improve. We set the hyper-parameters with best validation results. The results are shown in the following table:\n\n|       | tolokers | squirrel | twitch-gamers |\n|-------|----------|----------|---------------|\n| GCN   | 510      | 3790     | 1220          |\n| ICGNN | 33       | 225      | 49            |\n\nIt is clear that $\\text{ICG}_u-\\text{NN}$ consistently converges faster than GCN across all three benchmarks. Specifically, $\\text{ICG}_u-\\text{NN}$ converges approximately 15 times faster on the **tolokers** dataset, 17 times faster on the **squirrel** dataset, and 25 times faster on the **twitch-gamers** dataset compared to GCN, indicating a significant improvement in efficiency.\nWe will add this to the revised paper.\n\n> W4: To demonstrate the efficacy of the proposed initialization method, the paper should include a comparison with existing initialization methods, such as random initialization.\n\n**Answer:** We repeated the node classification experiments presented in **Table 2**, as described in **Appendix F.1**, using random initialization when optimizing the ICG, and compared the results to those obtained with eigenvector initialization.\n\n|                            | tolokers     | squirrel     | twitch-gamers |\n|----------------------------|--------------|--------------|---------------|\n| random initialization      | 83.30 ± 0.92 | 62.03 ± 0.98 | 64.73 ± 0.44  |\n| eigenvector initialization | 83.31 ± 0.64 | 62.10 ± 1.67 | 66.10 ± 0.42  |\n\nThe results indicate that eigenvector initialization generally outperforms random initialization across all datasets. While the improvements are minimal in some cases, such as with the tolokers and **squirrel** datasets, they are more pronounced in the **twitch-gamers** dataset.\n\nAdditionally, eigenvector initialization offers a practical advantage in terms of training efficiency. On average, achieving the same loss value requires 5% more time when using random initialization compared to eigenvector initialization. This efficiency gain further supports the utility of the proposed initialization method.\n\nWe will add these results and discussion to an ablation study section in the appendix.\n\n> Q1: Has the author evaluated the relationship between the model's performance and the cut-metric...\n\n**Answer:** **Figure 4** in **Appendix F.2** shows the relationship between test accuracy and the number of communities used, while **Figure 5** in **Appendix F.3** illustrates the relationship between cut-norm, Frobenius norm, and the number of communities. Using these figures, we present the accuracy as a function of the cut-norm, as requested by the reviewer:\n\n| cut-norm error | 0.09 | 0.1  | 0.11 | 0.13 | 0.27 |\n|----------|------|------|------|------|------|\n| accuracy | 61.3 | 62.1 | 57.2 | 55.8 | 53.2 |\n\nWe observe that as the cut-norm error increases, the test accuracy generally decreases. This indicates that a lower cut-norm, which corresponds to a more refined community structure, tends to result in higher accuracy of the model, as expected.\n \n> it is important to question whether this assumption holds in ther contexts, such as molecular graphs\n\nThe setting in this paper is a single large graph. Our setting does not extend to a dataset of many graphs. Molecular graphs are typically used in graph classification or regression, which is not appropriate for our method. This is emphasised in Line 44.", "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:
We thank the reviewers for their time and insightful comments. We respond to each concern in detail in our individual responses to the Reviewers, and provide here a summary of our rebuttal:

1. **Significance of contribution**: We want to stress that, while the numerical results are competitive and illustrate the merits of our proposed method, we believe that the theoretical results are the main contribution. **As far as we know, we are the first to bring the regularity lemma to the realm of practical numerical analysis**. We believe that this is the main focus of this paper. To emphasize the theoretical numerical analysis significance, we will add a review subsection about the regularity lemma and its computational aspects, which highlights the novelty of our paper (we already wrote it). We can copy this section as a comment to every reviewer that requests.

2. **Improved asymptotic analysis (Reviewer Z1J6 and 2roR)**: We managed to significantly improve the asymptotics of the ICG approximation bound in **Theorem 3.1**, which requires only a minor revision to the proof. **The multiplicative constant in (6) is now $\frac{3N}{2\sqrt{E}}$ instead of $\frac{3N^2}{2E}$**. Moreover, we show that this asymptotic is essentially tight. Namely, one can find a graph for which there does not exist any ICG that approximates it with an error less than $O(\frac{N}{\sqrt{KE}})$. This can be read off from **Theorem 1.2** in [1] (when converting their result to our definitions and notations). While this response is too short to show the proof, we are happy to send an anonymous PDF with the proof to the AC according to the rules and regulations of NeurIPS, so you can verify it.   This improved theorem leads to a better comparison to MPNN methods. Now, ICG requires $K>N^2/E$ to guarantee that ICG approximates any given graph.

3. **Additional experiments**:
    + **Comparison to graph coarsening methods (Reviewer hec5)** - We provide an empirical comparison in **Table 1** of **rebuttal.pdf** between our method and a variety of graph coarsening/summarization methods on the **reddit** and **flickr** datasets. ICG-NNs achieve state-of-the-art performance, further solidifying its effectiveness.
    + **Subgraph ICG-NN and ICG-NN on the large graph flickr (Reviewer Z1J6)** - To highlight the usage of subgraph sgd ICG-NN on large graphs, we conducted additional experiments using the **flickr** dataset, which is significantly larger than the datasets used in our initial submission. The results indicate that ICG-NNs with subgraph ICGm, using a 1% sampling rate, outperform competing methods that operate on the full graph.
    + **Run time analysis for the model's convergence (Reviewer hec5, XnC3)** - We measured the time (in seconds) until convergence for the GCN and $\text{ICG}_u-\text{NN}$ architectures across the node-classification tasks presented in **Appendix F.1, Table 2**. ICG-NNs converge significantly faster than GCN.
    + **Eigenvector initialization vs random initialization (Reviewer XnC3)** - We repeated the node classification experiments presented in **Table 2**, as described in **Appendix F.1**, using random initialization when optimizing the ICG, and compared the results to those obtained with eigenvector initialization. Eigenvector initialization improves performance.

4. **Choice of datasets (Reviewer hec5)**: We note that it is hard to find a dataset of large and non-sparse graphs. Currently, the community only focuses on sparse graphs in the context of large graphs when developing methods. As a result, researchers only publish sparse large datasets. We note that large graphs in real life are often not so sparse. For example, social networks can have an average degree of up to 1000, and transaction networks, user web activity monitoring networks, web traffic networks and Email networks can also be rather dense. Such networks, typically held by large companies, are not available to the public. Yet, knowing how to process large not-too-sparse graphs is of practical importance, and we believe that such graphs deserve a focus. As a first paper in this direction, it is hard to be competitive on datasets designed for sparse graphs. Still, our method performs remarkably well on large sparse graphs (in the paragraph in line 173  we give a possible explanation). We hope to see large dense real-life graphs open to the public in the future. 

5. **Comparison of ICG-NN to graph coarsening (Reviewer Z1J6 and hec5)**: We highlight the main differences, which we will include in the final version of the paper.
   + Graph coarsening methods do not typically stem from theoretical guarantees, whereas ICGs provably approximate the graph.
   + GNNs with local pooling do not asymptotically improve run-time, as the first layer operates on the full graph, while our method operates solely on the efficient data structure.
   + In pooling approaches, the graph is partitioned into disjoint, or slightly overlapping communities, each community collapses to a node, and a standard message passing scheme is applied on this coarse graph. In our approach, each community is large, and occupies a significant portion of the graph, and different communities have a large overlap. In ICG-NNs, each operation on the community features has a global receptive field in the graph. Moreover, ICG-NNs are not of message-passing type: the (flattened) community feature vector $F$ is symmetryless and is operated upon by a general MLP in the ICG-NN, while MPNNs operate by the same function on all edges.
   + Graph coarsening methods process representations on an iteratively coarsened graph. ICG-NNs also process the fine node information at every layer.

We hope that our answers, along with the new experiments, address your concerns. We are looking forward to a fruitful discussion period.

[1] Alon et al. Approximating sparse binary matrices in the cut-norm. Linear Algebra and its Applications, 2015.

Meta-review: The paper introduces the idea of Intersecting Communities Graph (ICG), which enables efficient learning on large non-sparse graphs. An offline preprocessing step (which runs in linear time in the number of edges) must be first used to construct the ICG, but after that approximate learning on the graph can be performed in time that is linear in the number of nodes (making it very useful in large dense graphs). The paper's theoretical contribution is significant, as it proves a constructive version of the Weak Regularity Lemma to efficiently construct an approximating ICG. Experiments also demonstrate the efficiency of the method across several datasets.

All reviewers seem to appreciate the technical contributions of the paper and the original ideas. While there were some questions from reviewers regarding practical use of the techniques (in which sparsity regimes it's more useful, how it compares with other large-scale graph learning techniques), reviewers seemed convinced by the rebuttals.
Decision: Accept (poster)