Learning on Large Graphs using Intersecting Communities

Authors: ben  finkelshtein
i̇smail i̇lkan ceylan
michael  bronstein
ron  levie
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 17:42:15

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.

Main paper: 
 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 to a memory complexity bottleneck. Specifically, considering a graph with N nodes and E edges, message-passing 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 a body of work with the ultimate goal of making the graph machine learning pipeline amenable to large graphs [24, 12, 13, 7, 65] .In this work, we take a drastically different approach to alleviate this problem and design a 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.e., cliques) such that the number of communities required to achieve a 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 standard message-passing paradigm -we propose a new class of neural networks acting on the ICG and on the set of nodes from the original input graph, which leads to an algorithm with memory and runtime complexity that is linear in the number nodes.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-supervised (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 8 ∼ 10 9 nodes and average node degree of 102 ∼ 103 [19] and do not fit into GPU memory. 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? Our answer to this question rests on an adaptation of the Weak Regularity Lemma [20, 38] which proves the existence of an approximating ICG in cut metric -a well-known graph similarity meausre 1 . 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 2 . We address this in Theorem 3.1, by proving that optimizing the error in Frobenius norm, a much easier optimization target, guarantees a 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 ϵ is K = ϵ -2 , independently of on any property of the graph, not even its size N . 3 This result allows us to design an efficient and numerically stable algorithm. Figure 1 shows an adjacency matrix with an inherent intersecting community structure, and our approximated ICG, which captures the statistics of edge densities, ignoring their granularity.How to effectively use ICG for efficient graph learning? We present a signal processing framework and deep neural networks based on the ICG representation (ICG-NN). As opposed to message-passing networks that require O(E) memory and time complexity, ICG-NNs operate in only O(N ) complexity. They involve node-wise operations to 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 a novel graph machine learning approach for large and non-sparse graphs which enables an O(N ) learning algorithm on ICG with one-off O(E) pre-processing cost for constructing ICG. • Technically, we prove a 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 a 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 is further supported by competitive performance against strong baseline models.2 A primer on graph-signals and the cut-metric Graph signals. We are interested in undirected (weighted or simple), featured graphs G = (N , E, S), where N denotes the set of nodes, E denotes the set of edges, and S denotes the node feature matrix, also called the signal. We will write N to represent the number of nodes and E to represent the number of edges. For ease of notation, we will assume that the nodes are indexed by [N ] = {1, . . . , N }. Using the graph signal processing convention, we represent the graphs in terms of a graph-signal G = (A, S), where A = (a i,j ) N i,j=1 ∈ R N ×N is the adjacency matrix, and S = (s i,j ) i∈[N ],j∈ [d] ∈ R N ×D is the D-channel signal. We assume that the graph is undirected, meaning that A is symmetric. The graph may be unweighted (with a i,j ∈ {0, 1}) or weighted (with a i,j ∈ [0, 1]). We additionally denote by s ⊤ n the n-th row of S, and denote S = (s n ) N n=1 . By abuse of notation, we also treat a signal S as the function S : [N ] → R D with S(n) = s n . 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 A i,: , and the j-th column by A :,j . The Frobenius norm of a square matrixM ∈ R N ×N is defined by ∥M ∥ F = 1 N 2 N n,m=1 |b n,m |2 , and for a signal S ∈ R N ×D by∥S∥ F = 1 N N n=1 D j=1 |s n,j | 2 .The Frobenius norm of a matrix-signal, with weights a, b > 0, is defined to be ∥(M , S)∥ F := a ∥M ∥ 2 F + b ∥S∥ 2 F . We define the degree of a weighted graph as deg(A) := N 2 ∥A∥ 2 F . In the special case of an unweighted graph we get deg(A) = E. The pseudoinverse of a full rank matrix M ∈ R N ×K , where N ≥ K, is M † = (M ⊤ M ) -1 M ⊤ . Cut-metric. The cut metric is a graph similarity, based on the cut norm. We show here the definitions for graphs of the same size; the extension for arbitrary pairs of graphs is based on graphons (see Appendix B.2). The definition of matrix cut norm is well-known, and we normalize it by a parameter 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 ∈ R N ×N , normalized by E, is defined to beEQUATIONThe signal cut norm of Z ∈ R N ×D is defined to beEQUATIONThe matrix-signal cut norm of (M , Z), with weights α > 0 and β > 0EQUATIONGiven two graphs A, A ′ , their distance in cut metric is the cut norm of their difference, namelyEQUATIONThe right-hand-side of ( 4) is interpreted as the difference between the edge densities of A and A ′ on the block on which these densities are the most dissimilar. Hence, cut-metric has a 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 ℓ 1 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, S)-(A ′ , S ′ )∥ □ .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 a 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 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, 33] , we use cut norm to derive new methods for a class of problems of interest. Namely, we introduce a 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 
intersecting community graphs: 
 Given a graph G with N nodes, for any subset of nodes U ⊂ [N ], denote by 1 U its indicator (i.e., 1 U (i) = 1 if i ∈ U and zero otherwise). We define an intersecting community graph-signal (ICG)with K classes (K-ICG) as a low rank graph-signal (C, P ) with adjacency matrix and signals given respectively byEQUATION)where r j ∈ R, f j ∈ R D ,Q] ⊂ R N ×N × R N ×D to be the set of all elements of the form (rqq ⊤ , qf ⊤ ), with q ∈ Q, r ∈ R and f ∈ R D . We call [Q] the soft rank-1 intersecting community graph (ICG) model corresponding to Q. Given K ∈ N, the subset [Q] K of R N ×N × R N ×D 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 ∈ N, any intersecting community graph-signal (C, P ) ∈ R N ×N × R N ×D in [Q] K can be represented by a triplet of community affiliation matrix Q ∈ R N ×K , community magnitude vector r ∈ R K , and community feature matrix F ∈ R K×D . In the matrix form, (C, P ) ∈ [Q] K if and only if it has the formC = Q diag(r)Q ⊤ and P = QF ,where diag(r) is the diagonal matrix in R K×K with r as its diagonal elements.The following theorem is a semi-constructive version of the Weak Regularity Lemma for intersecting communities. It is semi-constructive in the sense that the approximating graphon is not just assumed to exist, but is given as the result of an optimization problem with an "easy to work with" loss, namely, the Frobenius norm error. The theorem also extends the standard weak regularity lemma by allowing soft affiliations to communities instead of hard affiliations. Theorem 3.1. Let (A, S) be a D-channel graph-signal of N nodes, where deg(A) = E ′ . Let K ∈ N, δ > 0, and Q be a soft affiliation model. Consider the matrix-signal cut norm with weights α, β ≥ 0 not both zero, and the matrix-signal Frobenius norm with weights ∥(B, X)∥ F :=α N 2 E ∥B∥ 2 F + β ∥X∥ 2 F . Let m be sampled uniformly from [K], and let R ≥ 1 such that K/R ∈ N.Then, in probability 1 -1 R (with respect to the choice of m), for everyEQUATIONThe proof of Theorem 3.1 is given in Appendix B, where the theorem is extended to graphon-signals. Theorem 3.1 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 * , P * ) that corresponds to a small relative change in the optimal Frobenius error, leads to a small additive error in cut metric.ICGs vs. Message Passing. Until the rest of the paper we suppose for simplicity that the degree of the graph E ′ is equal to the number of edges E up to a constant scaling factor 0 < γ ≤ 1, namely E ′ = γE. Note that this is always true for unweighted graphs, where γ = 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 2 ). Denote the average node degree by d = E/N . To get a meaningful bound in (6), we must choose K > N 2 /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 is guaranteed to be more efficient than message passing for any graph in the semi-dense regime:d 2 > N (or equivalently E > N 3/2 ).Essential tightness of Theorem 3.1. In [2, Theorem 1.2] it was shown that the bound ( 6) is essentially tight in the following sense 4 . There exists a universal constant c (greater than 1/2312) such that for any N there exists an unweighted graph A ∈ R N ×N with deg(A) = E, such that any B ∈ R N ×N that approximates A with error ∥A -B∥ □;N,E ≤ 16 must have rank greater than c N 2 E . In words, there are graphs of E edges that we cannot approximate in cut metric by any ICG with K ≪ N 2 E . Hence, the requirement K ≫ N 2 /E ′ for a small cut metric error in (6) for any graph is tight.ICGs approximations of sparse graphs. In practice, many natural sparse graphs are amenable to low rank intersecting community approximations. For example, a simplistic model for how social networks are formed states that people connect according to shared characteristics (i.e. intersecting communities), like hobbies, occupation, age, etc [61] . Moreover, since ICGs can have negative community magnitudes r k , one can also construct heterophilic components (bipartite substructures) of graphs with ICGs5 . Hence, a social network can be naturally described using intersecting communities, even with K < N 2 /E. For such graphs, ICG approximations are more accurate than their theoretical bound (6) . In addition, Figure 5 in Appendix F.5 shows that in practice the Frobenius local minimizer, which does not give a small Frobenius error, guarantees small cut metric error even if K < N 2 /E. This means that Frobenius minimization is a practical approach for fitting ICGs also for sparse natural graphs. Moreover, note that in the experiments in Tables 2 and 1 we take K < N 2 /E and still get competitive performance with SOTA message passing methods.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 proofs 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
fitting icgs to graphs: 
 Let us fix the soft affiliation model to be all vectors q ∈ [0, 1] N . In this subsection, we propose algorithms for fitting ICGs to graphs based on Theorem 3.1.In view of Theorem 3.1, to fit a soft rank-K ICG to a graph in cut metric, we learn a triplet Q ∈ [0, 1] N ×K , r ∈ R K and F ∈ R K×D that minimize the Frobenius loss:EQUATIONwhere λ ∈ R is a scalar that balances the two loss terms. To implementQ ∈ [0, 1] N ×K in practice, we define Q = Sigmoid(R) for a learned matrix R ∈ R N ×K .Suppose that A is sparse with K 2 , 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 is O(N K 2 ). Hence, we would like to derive an optimization procedure that takes O(K 2 N + E) operations. However, the first term of (7) involves a subtraction of the low rank matrix Q diag(r)Q ⊤ from the sparse matrix A, which gives a matrix that is neither sparse nor low rank. Hence, a naïve optimization procedure would take O(N 2 ) operations. The next proposition shows that we can write the loss (7) in a form that leads to a O(K 2 N + KE) time and O(KN + E) space complexities. Proposition 4.1. Let A = (a i,j ) N i,j=1 be an adjacency matrix of a weighted graph with E edges. The graph part of the Frobenius loss can be written asA -Q diag(r)Q ⊤ 2 F = 1 N 2 Tr (Q ⊤ Q) diag(r)(Q ⊤ Q) diag(r) + ∥A∥ 2 F - 2 N 2 N i=1 j∈N (i) Q i,: diag(r) Q ⊤ :,j a i,j .Computing the right-hand-side and its gradients with respect to Q and r has a time complexity of O(K 2 N + KE), and a space complexity of O(KN + E).The proof is in Appendix C. We optimize Q, r, and F using gradient descent (GD) on ( 7) implemented via Proposition 4.1. After convergence, we further refine F by setting F = Q † S.In Appendix D we propose a good initialization for the GD minimization of (7) . Suppose that K is divisible by 3. Let Φ K/3 ∈ R N ×K/3 be the matrix consisting of the leading eigenvectors of A as columns, and Λ K/3 ∈ R K/3×K/3 the diagonal matrix of the leading eigenvalues. For each eigenvector ϕ with eigenvalue λ, consider the three soft indicatorsEQUATIONwith community affiliation magnitudesr 1 = 2λ ∥ϕ + ∥ 2 ∞ , r 2 = 2λ ∥ϕ -∥ 2 ∞ and r 3 = -λ ∥ϕ + + ϕ -∥ 2 ∞ 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 O(K -1/2 ). 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 O(E) 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.In many situations, we need to process large graphs for which E is too high to read to the GPU memory, but N K is not. These are the situation where processing graph-signals using ICGs is beneficial. However, to obtain the ICG we first need to 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 a random subgraph with M nodes.At each interation, we sample M ≪ N random nodes n := (n m ) M m=1 uniformly and independently from [N ] (with repetition). We construct the sub-graph A (n) ∈ R M ×M with entries a (n) i,j = a ni,nj , and the sub-signal S (n) ∈ R M ×K with entries s (n) i = s ni . We similarly define the sub-community affiliation matrix Q (n) ∈ [0, 1] M ×K with entries q (n) i,j = q ni,j . We consider the lossL (n) (Q (n) , r, F ) = A (n) -Q (n) diag(r)Q (n)⊤ 2 F + λ S (n) -Q (n) diag(r)F 2 F (9)which depends on all entries of F and r and on the n 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 ofL (n) (Q n , r, F ). Hence, ∇ Q L (n) (Q (n) ,r, F ) may only be nonzero for entries q n with n ∈ n. Proposition E.1 in Appendix E shows that the gradients of L (n) approximate the gradients of L.M N ∇ Q (n) L (n) ≈ ∇ Q (n) L, ∇ r L (n) ≈ ∇ r L, and ∇ F L (n) ≈ ∇ F L.Note that the stochastic gradients with respect to Q (n) approximate a scaled version of the full gradients.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: 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.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to 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 is a specific model and empirical evaluation, it 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to 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., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
learning with icg: 
 Given a graph-signal (A, S) and its approximating ICG (C, P ), the corresponding soft affiliations Q = (q k ) K k=1 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 (q k ) K k=1 . Next, we develop a signal processing framework for such signals. Graph signal processing with ICG. We develop a signal processing approach with O(N K) complexity for each elemental operation. Let Q ∈ R N ×K be a fixed community matrix. We call R N ×D the node space and R K×D 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(N KD).• Analysis is the mapping S → Q † S from the node space to the community space, in O(N KD).• Community processing refers to any operation that manipulates the community feature vector F (e.g., an MLP in which a linear operator requires KD × KD parameters or a Transformer) in O(K 2 D 2 ) operations.• Node processing is any function Θ that operates in the node space on nodes independently via Θ(S) := (θ(s n )) N n=1 , where θ : R D → R D ′ (e.g., an MLP) takes O(DD ′ ) operations. Node processing has time complexity of O(N DD ′ ).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 ∈ R K×D }. 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 caseQ † = (Q ⊤ Q) -1 Q ⊤ .Deep ICG Neural Networks. In the following, we propose deep architectures based on the elements of signal processing with an ICG, which take O(D(N K + K 2 D + N D)) operations at 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 + N D 2 ). General message passing layers, which define messages via a function applied on the concatenated pair of node features of each edge, take O(ED 2 ) 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 (ℓ) the dimension of the node features at layer ℓ and define the initial node representations H (0) = S and the initial community features F (0) = Q † S. The node features at layers 0 ≤ ℓ ≤ L -1 are defined byH (ℓ+1) = σ H (ℓ) W (ℓ) 1 + QΘ F (ℓ) W (ℓ) 2 , F (ℓ+1) = Q † H (ℓ) ,where Θ is a neural network (i.e. multilayer perceptron or MultiHeadAttention),W (ℓ) 1 , W (ℓ) 2 ∈ R D (ℓ) ×D (ℓ+1)are learnable matrices acting on signals in the node space, and σ is a non-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, whereF (ℓ) ∈ R K×D (ℓ)are taken directly as trainable parameters. Namely,H (ℓ+1) = σ H (ℓ) W (ℓ) s + QF (ℓ) W (ℓ) .We call this method ICG u -NN for the unconstrained community features. The motivation is that QF (ℓ) exhausts the space of all signals that are linear combinations of the communities. If the number of communities is not high, then this is a 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 a neural network Θ on latent representations. The term QF (ℓ) can hence be interpreted as a type of positional encoding that captures the community structure.ICG-NNs for spatio-temporal graphs. For a fixed graphs with varying node features, the ICG is fitted to the graph once 6 . Given that there are T training signals, each learning step with ICG-NN takes O(T N (K + D)) rather than O(T ED 2 ) for MPNNs. Note that T does not scale the preprocessing time. Hence, the time dimension amplifies the difference in efficiency between ICG-NNs and MPNNs.Question: Does the paper provide open access to the data and code, with sufficient instructions to 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. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiments: 
 We empirically validate our methods with the following experiments:7 • Runtime analysis (Section 6.1): We report the forward pass runtimes of ICG u -NN and GCN [30] , empirically validating the theoretical advantage of the former. We further extend this analysis in Appendices F.7 and F.8. • Node classification (Appendix F.1): We evaluate our method on real-world node classification datasets [43, 45, 36] , observing that the model performance is competitive with standard approaches. • Node classification using Subgraph SGD (Section 6.2 and Appendix F.3): We evaluate our subgraph SGD method (Section 4.3) to identify the effect of sampling on the model performance on the tolokers and Flickr datasets [43, 65] . We find the model's performance to be robust on tolokers and state-of-the-art on Flickr. • Spatio-temporal tasks (Section 6.3): We evaluate ICG u -NN on real-world spatio-temporal tasks [35] and obtain competitive performance to domain-specific baselines. • Comparison to graph coarsening methods (Appendix F.2): We provide an empirical comparison between ICG-NNs and a variety of graph coarsening methods on the Reddit [23] and Flickr [65] datasets, where ICG-NNs achieve state-of-the-art performance. • Additional experiments: We perform an ablation study over the number of communities (Appendix F.4) and the choice of initialization in Section 4.2 (Appendix F.6). We moreover experimentally 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? Setup. We compare the forward pass runtimes of our signal processing pipeline (ICG u -NN) and GCN [30] on Erdős-Rényi ER(n, p(n) = 0.5) graphs with up to 7k nodes. Node features are independently drawn from U [0, 1] and the initial feature dimension is 128. Both models use a hidden dimension of 128, 3 layers and an output dimension of 5.Results. Figure 2 reveals a strong square root relationship between the runtime of ICG u -NN and the runtime of GCN. This aligns with our expectations, as the time complexity of GCN is O(E), while the time complexity of ICG-NNs is O(N ), highlighting the computational advantage of using ICGs. We complement this analysis with experiments using sparse Erdős-Rényi graphs in Appendix F.7. Setup. We evaluate ICG u -NN on the non-sparse graphs tolokers [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.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 is removed, the performance stops degrading. These results further support our Proposition E.1 in Appendix E about the error between subgraph gradients and full-graph gradients of the Frobenius loss, and establish ICG-NNs as a viable option for learning on large graphs. Setup & baselines. We evaluate ICG-NN and ICG u -NN on real-world traffic networks, METR-LA and PEMS-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 are 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 forecastings. The baselines DCRNN [35] , GraphWaveNet [60] , AGCRN [8] , T&S-IMP, TTS-IMP, T&S-AMP, and TTS-AMP [15] , are adopted from [15] . 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 λ = 0 in ( 7)). Additionally, we use the Adam optimizer and detail all hyperparameters in Appendix I.Results. Table 1 shows that ICG-NNs achieve competitive performance when compared to methods that are specially tailored for spatio-temporal data such as DCRNN, GraphWaveNet 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 -2 ), 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 statistics and computer science [1, 62] . Our approach can be interpreted as fitting a stochastic-block-model (SBM) to a 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 O(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, we are the first to propose a SBM fitting algorithm based on the weak regularity lemma. For a survey on SBMs we refer the reader to [32] .The Weak Regularity Lemma. The Regularity Lemma is a 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 ϵ is uniformly Theorem 2] proposes an algorithm for finding the approximating ICG, the algorithm takes 2 O(N 2 K) time to find this minimizer 9 . This time complexity is too high to be practical in real-world problems. Alternatively, since the cut metric is defined via a maximization process, finding a minimizing ICG by directly optimizing cut metric via a GD approach involves a min-max problem, which appears numerically problematic in practice. Moreover, computing cut norm is NP-hard [3, 44] . Instead, we introduce a way to bypass the need to explicitly compute the cut norm, finding a K community ICG with error O(K -1/2 ) in the cut metric by minimizing the Frobenius norm. We note that for the Szemerédi (non-weak) regularity lemma [49] , it was shown by Alon et al. [4] that a regular partition with error < ϵ into non-intersecting communities (the analogue to ICG in 8 In the above papers the lemma is formulated for non-intersecting blocks i,j ri,j1U i 1U j , where • ∪{Uj} = [N ], with error ϵ = O (log(K)) -1/2 . The intersecting community case is an intermediate step of the proof. 9 One needs to convert the scaling of the Frobenius and cut norms used in [20] to our scaling to see this.O(K -1/2 ) 8 . While [20,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 for deployment on contemporary processors [24, 12, 13, 7, 65] . 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 in unintended ways.GNNs with local pooling. Local graph pooling methods, e.g., [63, 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-frequency content of the signal when projecting upon the communities, as we also have node-wise operations at the fine level.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 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.In terms of computational efficiency, GNNs with local pooling do not asymptotically improve runtime, 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, j r j 1Uj (n)1 Uj (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 r j , that can be negative and hence allow a more expressive decoding.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?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 are accompanied by error bars, confidence 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 or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
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 a 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 O(E) 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 a 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 a 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.Let G = {N , E} be a graph and P = {N 1 , . . . , N k } be a partition of N . The partition is calledequipartition if ||N i | -|N j || ≤ 1 for every 1 ≤ i, j ≤ k.For any two subsets U, S ⊂ N , the number of edges from U to S are denoted by e G (U, S). Given two node set U, S ⊂ N , if the edges between N i and N j were distributed randomly, then, the number of edges between U and S would have been close to the expected valuee P(U ,S) := k i=1 k j=1 e G (N i , N j ) |N i | |N j | |N i ∩ U | |N j ∩ S| .Thus, the irregularity, which measure of how non-random like the edges between {N j } are, is defined to be irregEQUATION)Theorem A.1 (Weak Regularity Lemma [20] ). For every ϵ > 0 and every graph G = (N , E), there is an equipartitionP = {N 1 , . . . , N k } of N into k ≤ 2 c/ϵ 2 classes such that irreg G (P) ≤ ϵ.Here, c is a universal constant that does not depend on G and ϵ.The weak regularity lemma states that any large graph G can be represented by the weighted graph G ϵ with node set N ϵ = {N 1 , . . . , N k }, where the edge weight between the nodes N i and N j ise G (Ni,Nj )|Ni|,|Nj | , which depicts a smaller, coarse-grained version of the large graph. The "large-scale" structure of G is given by G ϵ , and the number of edges between any two subsets of nodes U i ⊂ N i and U j ⊂ N j is close to the "expected value" e P(Ui,Uj ) . Hence, the deterministic graph G "behaves" as if it was randomly sampled from the "stochastic block model" G ϵ .It can be shown that irregularity coincides with error in cut metric between the graph and its coarsening SBM. Namely, to see how the cut-norm is related to irregularity (10) , consider a graphon W G induced by the graph G = {N , E}. Let P = {N 1 , . . . , N k } be an equipartition of N . Consider the graph G P defined by the adjacency matrix A P = (a P i,j )EQUATIONa P i,j = e G (N qi , N qj ) |N qi | , N qj ,where N qi ∈ P is the class that contains node i. Now, it can be verified that∥W G -W G P ∥ □ = irreg G (P).Hence, the weak regularity lemma can be formulated with cut norm instead of irregularity.In this section we prove a constructive weak regularity lemma for graphon-signals, where Theorem 3. For m, J ∈ N, the L 2 norm of a measurable functionf = (f i ) j i=1 : [0, 1] m → R J , where f i : [0, 1] m → R, is defined to be ∥f ∥ 2 = J j=1 [0,1] m |f j (x)| 2 dx.A graphon [11, 37] can be seen as a weighted graph with a "continuous" node set [0, 1]. The space of graphons W is defined to be the set of all measurable symmetric function W : [0, 1] 2 → [0, 1], W (x, y) = W (y, x). Each edge weight W (x, y) ∈ [0, 1] of a graphon W ∈ W can be seen as the probability of having an edge between nodes x and y. Graphs can be seen as special graphons. Let I m = {I 1 , . . . , I m } be an interval equipartition: a partition of [0, 1] into disjoint intervals of equal length.A graph with an adjacency matrix A = (a i,j ) N i,j=1 induces the graphon W A , defined by W A (x, y) = a ⌈xm⌉,⌈ym⌉ 10 . Note that W A is piecewise constant on the partition I m . We hence identify graphs with their induced graphons. A graphon can also be seen as a generative model of graphs. Given a graphon W , a corresponding random graph is generated by sampling i.i.d. nodes {u n } from the graphon domain [0, 1], and connecting each pair u n , u m in probability W (u n , u m ) 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] 2 → [0, 1] and s : [0, 1] → [0, 1] D , 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 be [0, 1] D -valued. Given a discrete signal S : [N ] → [0, 1] D , we define the induced signal s S over [0, 1] by s S (x) = s ⌈xm⌉ . We define the Frobenius distance between two graphon-signals (W, s) and (W ′ , s ′ ) simply as their L 2 distance, namely,∥(W, s) -(W ′ , s ′ )∥ F := a ∥W -W ′ ∥ 2 2 + b D j=1 s j -s ′ j 2 2 (11)for some a, b > 0.The cut metric is a natural notion of graph similarity, based on the cut norm. The graphon-signal cut norm was defined in [33] , extending the standard definition to a graphon with node features.EQUATIONThe signal cut norm of s = (s 1 , . . . , s D ) ∈ (L 2 [0, 1]) D is defined to beEQUATION)The graphon-signal cut norm of (W, s)EQUATIONGiven two graphons W, W ′ , their distance in cut metric is the cut norm of their difference, namelyEQUATIONThe right-hand-side of ( 15) is interpreted as the similarity between the adjacencies W and W ′ on the block on which they are the most dissimilar. The graphon-signal cut metric is similarly defined to be ∥(W, s) -(W ′ , s ′ )∥ □ . The cut metric between two graph-signals 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 a special case of graphon-signal cut norm for induced graph-signals.Here, we define ICGs for graphons. Denote by χ the set of all indicator function of measurable subset of[0, 1] χ = {1 u | u ⊂ [0, 1] measurable}. Definition B.2. A set Q of bounded measurable functions q : [0, 1] → R that contains χ is called a soft affiliation model. Definition B.3. Let D ∈ N. Given a soft affiliation model Q, the subset [Q] of L 2 [0, 1] 2 ×(L 2 [0, 1]) Dof all elements of the form (rq(x)q(y), bq(z)), with q ∈ Q, r ∈ R and b ∈ R D , is called the soft rank-1 intersecting community graphon (ICG) model corresponding to Q. Given K ∈ N, the subset[Q] K of L 2 [0, 1] 2 × (L 2 [0, 1]) D of all linear combinations of K elements of [Q] is called the soft rank-K ICG model corresponding to Q. Namely, (C, p) ∈ [Q] K if and only if it has the form C(x, y) = K k=1 r k q k (x)q k (y) and p(z) = K k=1 b k q k (z)for (q k ) K k=1 ∈ Q K called the community affiliation functions, (r k ) K k=1 ∈ R K called the community affiliation magnitudes, and (b k ) K k=1 ∈ R K×D called the community features.The following theorem is the semi-constructive version of the weak regularity lemma for intersecting communities of graphons. Recall that α and β denote the weights of the graphon-signal cut norm (14) . Consider the graphon-signal Frobenius norm with weights α ∥W ∥2 F + β D j=1 ∥s j ∥ 2 F . Then, in probability 1 -1 R (with respect to the choice of m), for every (C * , p * ) ∈ [Q] m , if ∥(W, s) -(C * , p * )∥ F ≤ (1 + δ) min (C,p)∈[Q]n ∥(W, s) -(C, p)∥ F then ∥(W, s) -(C * , p * )∥ □ ≤ 3 2 α 2 ∥W ∥ 2 F + αβ ∥s∥ F + αβ∥W ∥ 2 F + β 2 ∥s∥ F R K + δ.In this subsection we prove the constructive weak graphon-signal regularity lemma.The classical proof of the weak regularity lemma for graphons is given in [38] . The lemma is a 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 [38, Lemma 4] , even though we do not use this result directly.). Let K 1 , K 2 , . . . be arbitrary nonempty subsets (not necessarily subspaces) of a real Hilbert space H. Then, for every ϵ > 0 and g ∈ H there is m ≤ ⌈1/ϵ 2 ⌉ andEQUATIONNext, we show how to modify the result to be written explicitly with an approximate minimizer of a Hilbert space norm minimization problem. The proof follows the step of [38] with some modifications required for explicitly constructing an approximate optimizer. Lemma B.3. Let {K j } j∈N be a sequence of nonemply subsets of a real Hilbert space H and let δ ≥ 0. Let K > 0, let R ≥ 1 such that K/R ∈ N, and let g ∈ H. Let m be randomly uniformly sampled from [K]. Then, in probability 1 -1 R (with respect to the choice of m), any vector of the formg * = m j=1 γ j f j such that γ = (γ j ) m j=1 ∈ R m and f = (f j ) m j=1 ∈ K 1 × . . . × K mthat gives a close-to-best Hilbert space approximation of g in the sense thatEQUATIONwhere the infimum is over γ ∈ R m and f ∈ K 1 × . . . × K m , also satisfies∀w ∈ K m+1 , |⟨w, g -g * ⟩| ≤ ∥w∥ ∥g∥ R K + δ. Proof. Let K > 0. Let R ≥ 1 such that K/R ∈ N.For every k, letη k = (1 + δ) inf γ,f ∥g - k i=1 γ i f i ∥ 2where the infimum is overγ = {γ 1 , . . . , γ k } ∈ R k and f = {f 1 , . . . , f k } ∈ K 1 × . . . × K k . Note that ∥g∥ 2 ≥ η1 1+δ ≥ η2 1+δ ≥ . . . ≥ 0.Therefore, there is a subset of at least (1-1 R )K + 1 indices m in [K] such that η m ≤ η m+1 + R(1+δ) K ∥g∥ 2 . Otherwise, there are K R indices m in [K] such that η m+1 < η m -R(1+δ) K ∥g∥2 , which means thatη K < η 1 - K R R(1 + δ) K ∥g∥ 2 ≤ (1 + δ) ∥g∥ 2 -(1 + δ) ∥g∥ 2 = 0,which is a contradiction to the fact that η K ≥ 0.Hence, there is a setEQUATIONthat satisfies ∥g -EQUATION)Let w ∈ K m+1 . By the definition of η m+1 , we have for every t ∈ R,∥g -(g * + tw)∥ 2 ≥ η m+1 1 + δ ≥ ∥g -g * ∥ 2 1 + δ - R K ∥g∥ 2 .This can be written asEQUATIONThe discriminant of this quadratic polynomial is4 ⟨w, g -g * ⟩ 2 -4 ∥w∥ 2 R K ∥g∥ 2 + (1 - 1 1 + δ ) ∥g -g * ∥ 2and it must be non-positive to satisfy the inequality (20), namely4 ⟨w, g -g * ⟩ 2 ≤ 4 ∥w∥ 2 R K ∥g∥ 2 + (1 - 1 1 + δ ) ∥g -g * ∥ 2 ≤ 4 ∥w∥ 2 R K ∥g∥ 2 + (1 - 1 1 + δ )η m ≤ 4 ∥w∥ 2 R K ∥g∥ 2 + (1 - 1 1 + δ )(1 + δ) ∥g∥ 2 which proves ⟨w, g -g * ⟩ ≤ ∥w∥ ∥g∥ R K + δ.This is also true for -w, which concludes the proof.For two functions f, g : [0, 1] → R, we denote by f ⊗ g : [0, 1] 2 → R the function f ⊗ g(x, y) = f (x)g(y).We recall here Theorem B.1 for the convenience of the reader. ) ∈ [Q] m , if ∥(W, s) -(C * , p * )∥ F ≤ (1 + δ) min (C,p)∈[Q]n ∥(W, s) -(C, p)∥ F then ∥(W, s) -(C * , p * )∥ □ ≤ 3 2 α 2 ∥W ∥ 2 F + αβ ∥s∥ F + αβ∥W ∥ 2 F + β 2 ∥s∥ F R K + δ.The proof follows the techniques of a part of the proof of the weak graphon regularity lemma from [38] , while tracking the approximate minimizer in our formulation of Lemma B.3. This requires a probabilistic setting, and extending to soft indicators models. We note that the weak regularity lemma in [38] is formulated for non-intersecting blocks, but the intersecting community version is an intermediate step in its proof.Proof. Let us use Lemma B.3, with H = L 2 [0, 1] 2 × (L 2 [0, 1]) D with the weighted inner product ⟨(W, s), (W ′ , s ′ )⟩ = α [0,1] 2 W (x, y)W ′ (x, y)dxdy + β D j=1 [0,1] s j (x)s ′ j (x)dx,and corresponding norm α ∥W ∥2 F + β D j=1 ∥s j ∥ 2 Fand corresponding weighted inner product, and K j = [Q]. Note that the Hilbert space norm is the Frobenius norm in this case. In the setting of the lemma, we take g = (W, s), and g * ∈ [Q] m . By the lemma, in the event of probability 1 -1/R, any approximate Frobenius minimizer (C * , p * ), namely, that satisfies ∥(W, s)-(C * , p * )∥ F ≤ (1 + δ) min (C,p)∈[Q]m ∥(W, s) -(C, p)∥ F , also satisfies ⟨(T, y), (W, s) -(C * , p * )⟩ ≤ ∥(T, y)∥ F ∥(W, s)∥ F R K + δ for every (T, y) ∈ [Q].Hence, for every choice of measurable subsets S, T ⊂ [0, 1], we haveS T (W (x, y) -C * (x, y))dxdy = 1 2 S T (W (x, y) -C * (x, y))dxdy + T S (W (x, y) -C * (x, y))dxdy = 1 2 S∪T S∪T (W (x, y) -C * (x, y))dxdy - S S (W (x, y) -C * (x, y))dxdy - T T (W (x, y) -C * (x, y))dxdy ≤ 1 2α ⟨(1 S∪T ⊗ 1 S∪T , 0), (W, s) -(C * , p * )⟩ + 1 2α ⟨(1 S ⊗ 1 S , 0), (W, s) -(C * , p * )⟩ + 1 2α ⟨(1 T ⊗ 1 T , 0), (W, s) -(C * , p * )⟩ ≤ 1 2α ∥(W, s)∥ F ∥(1 S∪T ⊗ 1 S∪T , 0)∥ F + ∥(1 S ⊗ 1 S , 0)∥ F + ∥(1 T ⊗ 1 T , 0)∥ F R K + δ ≤ 3 2α α∥W ∥ 2 F + β ∥s∥ F √ α R K + δHence, taking the supremum over S, T ⊂ [0, 1], we also haveα ∥W -C * ∥ □ ≤ 3 2 α 2 ∥W ∥ 2 F + αβ ∥s∥ F R K + δ.Similarly, for every measurable T ⊂ [0, 1] and every standard basis element b = (δ j,i ) D i=1 for any j ∈ [D],T (s j (x) -p * j (x))dx = 1 β ⟨(0, b1 T ), (W, s) -(C * , p * )⟩ ≤ 1 β ∥(W, s)∥ F ∥(0, b1 T )∥ F R K + δ ≤ 1 β α∥W ∥ 2 F + β ∥s∥ F β R K + δ,so, taking the supremum over T ⊂ [0, 1] independently for every j ∈ [D], and averaging over j ∈ [D], we getβ ∥s -p * ∥ □ ≤ αβ∥W ∥ 2 F + β 2 ∥s∥ F R K + δ.Overall, we get ∥(W, s) -(C * , p * )∥ □ ≤ 3 2 α 2 ∥W ∥ 2 F + αβ ∥s∥ F + αβ∥W ∥ 2 F + β 2 ∥s∥ F R K + δ.∥(A, S) -(C * , P * )∥ □,N,E ≤ 3 2 α ′2 N 4 E 2 E N 2 + α ′ β ′ N 2 E + α ′ β ′ N 2 E E N 2 + β ′2 R K + δ ≤ C N √ E R K + δwhere, since α ′ + β ′ = 1, and by convexity of the square root,C = 3 2 √ α ′ + β ′ ≤ 3 2 √ α ′ + 3 2 β ′ ≤ 3 2 α ′ + β ′ = 3 2 .The only thing left to do is to change the notations α ′ → α and β ′ → β.Here, we prove Proposition 4.1. For convenience, we recall the proposition.Proposition 4.1. Let A = (a i,j ) N i,j=1 be an adjacency matrix of a weighted graph with E edges. The graph part of the Frobenius loss can be written asA -Q diag(r)Q ⊤ 2 F = 1 N 2 Tr (Q ⊤ Q) diag(r)(Q ⊤ Q) diag(r) + ∥A∥ 2 F - 2 N 2 N i=1 j∈N (i) Q i,: diag(r) Q ⊤ :,j a i,j .Computing the right-hand-side and its gradients with respect to Q and r has a time complexity of O(K 2 N + KE), and a space complexity of O(KN + E).Proof. The loss can be expressed asEQUATION, and getA -Q diag(r)Q ⊤ 2 F = 1 N 2 N i,j=1 Q i,: diag(r) Q ⊤ :,j 2 + 1 N 2 N i=1 j∈N (i) a 2 i,j -2Q i,: diag(r) Q ⊤ :,j a i,j = Q diag(r)Q ⊤ 2 F + 1 N 2 N i,j=1 a 2 i,j - 2 N 2 N i=1 j∈N (i) Q i,: diag(r) Q ⊤ :,j a i,j = 1 N 2 Tr Q diag(r)Q ⊤ Q diag(r)Q ⊤ + 1 N 2 N i,j=1 a 2 i,j - 2 N 2 N i=1 j∈N (i) Q i,: diag(r) Q ⊤ :,j a i,j = 1 N 2 Tr Q ⊤ Q diag(r)Q ⊤ Q diag(r) + 1 N 2 N i,j=1 a 2 i,j - 2 N 2 N i=1 j∈N (i) Q i,: diag(r) Q ⊤ :,j a i,jThe last equality follows the identity ∀B,D ∈ R N ×K : Tr(BD ⊤ ) = Tr(D ⊤ B), with B = Q diag(r)Q ⊤ Q diag(r) and D = Q ⊤ .The middle term in the last line is constant and can thus be omitted in the optimization process. The leftmost term in 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 O(K 2 N ) and the largest matrix held in memory is of size O(KN ). The rightmost term is calculated by message-passing, which has time complexity of O(KE). Thus, Computing the right-hand-side and its gradients with respect to Q and r has a time complexity of O(K 2 N + KE) and a space complexity of O(KN + E).Next, we propose a good initialization for the GD minimization of (7) . For that, we consider a corollary of the constructive soft weak regularity for grapohns, with the signal weight in the cut norm set to β = 0, using all L 2 [0, 1] functions as the soft affiliation model, and taking relative Frobenius error with δ = 0. In this case, the best rank-K approximation theorem (Eckart-Young-Mirsky Theorem [51, Theorem 5.9]), the minimizer of the Frobenius error is the projection of W upon its leading eigenvectors. This leads to the following corollary. ∥A -C * ∥ □;N,E ′ ≤ 3N 2 √ E ′ R K .The initialization is based on Corollary D.1 as follows. We consider the leading K/3 eigenvectors, assuming K is divisible by 3, for reasons that will become clear shortly. Hence, forC = Φ K/3 Λ K/3 Φ T K/3, where Φ K/3 ∈ R N ×K/3 is the matrix consisting of the leading eigenvectors of A as columns, and Λ K/3 ∈ R K/3×K/3 the diagonal matrix of the leading eigenvalues, we haveEQUATIONTo obtain soft affiliations with values in [0, 1], we now initialize Q as described in (8) .In this section we prove that the gradients of the subgraph SGD approximate the gradients of the full GD method. Proposition E.1. Let 0 < p < 1. Under the above setting, if we restrict all entries of C, P , Q, r and F to be in [0, 1], then in probability at least 1 -p, for every k∈ [K], d ∈ [D] and m ∈ [M ] ∇ q nm,k L - M N ∇ q nm,k L (n) ≤ 4 N 2 log(1/p 3 ) + 2 log(N ) + 2 log(K) + 2 log(2) M , ∇ r k L -∇ r k L (n) ≤ 4 2 log(1/p 1 ) + 2 log(N ) + 2 log(K) + 2 log(2) M , ∇ f k,d L -∇ f k,d L (n) ≤ 4λ D 2 log(1/p 2 ) + 2 log(K) + 2 log(D) + 2 log(2) M .Proposition E.1 means that the gradient with respect to r and F computed at 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 N . To use the same entry-wise learning rate in 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 a factor M/N ) by time complexity (increasing it by a 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.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 L (n) .To avoid tensor notations, we treat by abuse of notation the gradient of a function as a linear operator. Recall that the differential D r T = D r T (r ′ ) of the function T : R R → R U at the point r ′ ∈ R R is the unique linear operator R R → R U that describes the linearization of T about r ′ viaT (r ′ + ϵr ′′ ) = T (r ′ ) + ϵD r T r ′′ + o(ϵ)where ϵ ∈ R. Given an inner product in R R , the gradient ∇ r T = ∇ r T (r ′ ) ∈ R U ×R of the function T : R R → R U at the point r ′ ∈ R R is defined to be the vector (guaranteed to uniquely exist by the Riesz representation theorem) that satisfies D r T r ′′ = ⟨r ′′ , ∇ r T ⟩ for every r ′′ ∈ R R . Here, the inner product if defined row-wise by⟨r ′′ , ∇ r T ⟩ := ⟨r ′′ , ∇ r T [u, :]⟩ U u=1 ,where T [u, :] is the u-th row of ∇ r T . In our analysis, by abuse of notation, we identify ∇ r T with D r T for a fixed given inner product.Define the inner product between matrices⟨B, D⟩ 2 = i,j b i,j d i,j . Denote L(C, P ) = ∥A -C∥ 2 F + λ ∥S -P ∥ 2 F .First, the gradient of ∥A -C∥ 2 F with respect to C is∇ C ∥A -C∥ 2 F = - 2 N 2 (A -C),which is identified by abuse of notation by the linear functionalR N 2 → R D → ∇ C ∥A -C∥ 2 F (D) = D, - 2 N 2 (A -C) 2 .Similarly,∇ P ∥S -P ∥ 2 F = - 2 N D (S -P ) : R N D → R.Given any parameter z ∈ R R on which the graph C = C(z) and the signal P = P (z) depend, we haveEQUATIONwhere∇ z C : R R → R N 2 and ∇ z C ∈ R R → R N Dare linear operators, and the products in ( 22) are operator composition, namely, in coordinates it is elementwise multiplication (not matrix multiplication).Let us now compute the gradients of C = Q diag(r)Q ⊤ and P = QF with respect to Q, r and F in coordinates. We have ∇ r k c i,j = q i,k q j,k , and∇ q m,k c i,j = r k δ i-m q j,k + r k δ j-m q i,k ,where δ l is 1 if l = 1 and zero otherwise. Moreover,EQUATION∇ q m,k p i,d = f k,d δ i-m .Hence,∇ r k L = 2 N 2 N i,j=1(c i,j -a i,j )q i,k q j,k ,EQUATION∇ f k,l L = λ 2 N D N i=1 (p i,l -s i,l )q i,k .Similarly,EQUATION∇ f k,l L (n) = λ 2 M D M i=1 (p ni,l -s ni,l )q ni,k .We next derive the convergence analysis, based on Hoeffding's Inequality and two Monte-Carlo approximation lemmas.Theorem E.2 (Hoeffding's Inequality). Let Y 1 , . . . , Y M be independent random variables such that a ≤ Y m ≤ b almost surely. Then, for every k > 0,P 1 M M m=1 (Y m -E[Y m ]) ≥ k ≤ 2 exp - 2k 2 M (b -a) 2 .The following is a standard Monte Carlo approximation error bound based on Hoeffding's inequality.Lemma E.3. Let {i m } M m=1 be uniform i.i.d in [N ]. Let v ∈ R N be a vector with entries v n in the set [-1, 1]. Then, for every 0 < p < 1, in probability at least 1 -p 1 M M m=1 v im - 1 N N n=1 v n ≤ 2 log(1/p) + 2 log(2) M .Proof. This is a direct result of Hoeffding's Inequality on the i.i.d. variables {v im } M m=1 .The next lemma derives a Monte Carlo approximation error bound based on Hoeffding's inequality for 2D arrays, in case one samples only 1D independent sample points, and the 2D sample points are all pairs of the 1D points (which are hence no longer independent).Lemma E.4. Let {i m } M m=1 be uniform i.i.d in [N ]. Let A ∈ R N ×N be symmetric with a i,j ∈ [-1, 1]. Then, for every 0 < p < 1, in probability more than 1 -p 1 N 2 N j=1 N n=1 a j,n - 1 M 2 M m=1 M l=1 a im,i l ≤ 2 2 log(1/p) + 2 log(N ) + 2 log(2) M .Proof. Let 0 < p < 1. For each fixed n ∈ [N ], consider the independent random variables Y n m = a im,n , withE(Y n m ) = 1 N N j=1 a j,n ,and -1 ≤ Y m ≤ 1. By Hoeffding's Inequality, for k = 2 log(1/p)+2 log(N )+2 log(2), we have1 N N j=1 a j,n - 1 M M m=1 a im,n ≤ kin an event E n of probability more than 1 -p/N . Intersecting the events {E n } N n=1 , we get∀n ∈ [N ] : 1 N N j=1 a j,n - 1 M M m=1 a im,n ≤ k in the event E = ∩ n E n probability at least 1 -p.Hence, by the triangle inequality, we also have in the eventE 1 N M M l=1 N j=1 a j,i l - 1 M 2 M l=1 M m=1 a im,i l ≤ k, and 1 N 2 N n=1 N j=1 a j,n - 1 N M N n=1 M m=1 a im,n ≤ k.Hence, by the symmetry of A and by the triangle inequality,1 N 2 N n=1 N j=1 a j,n - 1 M 2 M l=1 M m=1 a im,i l ≤ 2k.Now, since all entries of A, S, C, P , Q, r and F are in [0, 1], we may use Lemmas E.3 and E.4 to derive approximation errors for the gradients of L. Specifically, for any 0 < p 1 < 1, for every k ∈ [K] there is an event A k of probability at least 1 -p 1 such that∇ r k L -∇ r k L (n) ≤ 4 2 log(1/p 1 ) + 2 log(N ) + 2 log(2) M .Moreover, for every k ∈ [K] and j ∈ [D], and every 0 < p 2 < 1 there is an event C k,j of probability at least 1 -p 2 such that∇ f k,l L -∇ f k,l L (n) ≤ 4λ D 2 log(1/p 2 ) + 2 log(2) M .For the approximation analysis of ∇ q nm,l L, note that the index n m is random, so we derive a uniform convergence analysis for all possible values of n m . For that, for every n ∈ [N ] and k ∈ [K], define the vector∇ q n,k L (n) = 2 M 2 M j=1 (c n,nj -a n,nj )c k q nj ,k + 2 M 2 N i=1 (c ni,n -a ni,n )c k q ni,k + λ 2 M D D d=1 (p n,d -s n,d )f k,d , Note that ∇ q n,k L (n)is not a gradient of L (n) (since if n is not a sample from {n m } the gradient must be zero), but is denoted with ∇ for its structural similarity to ∇ q nm,k L (n) . Let 0 < p 3 < 1. By Lemma E.3, for every k ∈ [K] there is an event B k of probability at least 1 -p 3 such that for every n ∈ [N ]∇ q n,k L - M N ∇ q n,k L (n) ≤ 4 N 2 log(1/p 3 ) + 2 log(N ) + 2 log(2) M .This means that in the event B k , for every m ∈ [M ] we have∇ q nm ,k L - M N ∇ q nm,k L (n) ≤ 4 N 2 log(1/p 3 ) + 2 log(N ) + 2 log(2) M .Lastly, given 0 < p < 1, choosing p 1 = p 3 = p/3K and p 2 = p/3KD and intersecting all events for all corrdinates gives and event E of probability at least 1 -p such thatEQUATION∇ q nm,k L - M N ∇ q nm,k L (n) ≤ 4 N 2 log(1/p 3 ) + 2 log(N ) + 2 log(K) + 2 log(2) M .Setup. We evaluate ICG-NN and ICG u -NN on the non-sparse graphs tolokers [43] , squirrel [45] and twitch-gamers [36] . We follow the 10 data splits of Platonov et 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. [34] for twitch-gamers. 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] , H 2 GCN [69] , GPR-GNN [14] , LINKX [36] , GloGNN [34] are taken from Platonov et 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 I.Results. All results are 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-passing neural networks.In this section we highlight the main differences and similarities between graph coarsening methods and ICG-NNs, followed by an empirical comparison over large graphs.Graph coarsening methods [18, 25] , graph condensation methods [26] and graph summarization methods [68] replace the original graph by one which has fewer nodes, with different features and a different topological structure, while sometimes preserving certain properties, such as the degree distribution [68] .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 structure by apply message-passing on the coarsened graph. Condensation methods require O(EM ) operations [26, 67, 56] , where E is the number of edges of the original graph and M is the number of nodes of the condensed graph. Conversely, ICGs estimate the ICG with O(K 2 N + KE) operations, where K is typically smaller than M .Node processing. Graph coarsening methods process representations on an iteratively coarsened graph, while ICG-NN also process the fine node information at every layer.Graphs larger than 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.Setup. We evaluate ICG-NN and ICG u -NN 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 [67, 56] . We use the Adam optimizaer and report all hyperparameters in Appendix I.Results. ICG-NNs present state-of-the-art performance in Table 3 when compared to a vareity of both graph coarsening methods and graph condensation methods, further solidifying its effectiveness. Setup. We evaluate ICG-NN and ICG u -NN on the large graph Flickr [65] . We follow the splits of [67] and report the accuracy and standard deviation. We set the ratio of condensation r = M N to 1%, where N and M are the number of nodes in the graph and the number of sampled nodes.The 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 [67, 56] . We use the Adam optimizaer and report all hyperparameters in Appendix I.Results. Table 4 shows that ICG u -NN with subgraph ICGm with 1% sampling rate, achieves competitive performance with coarsening and condensation methods that operate on the full graph in memory.Setup. We evaluate ICG-NN and ICG u -NN on 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 4 shows several key trends across both datasets. First, as anticipated, when a 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 a relatively small number of communities, specifically 25 for tolokers and 75 for squirrel. Lastly, using a large number of communities does not appear to negatively impact performance.While the cut norm is the theoretical target of the ICG approximation, it is expensive to estimate directly. However, Theorem 3.1 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 compared to eigenvector initialization. This efficiency gain further supports the utility of the proposed initialization method.In this subsection, we compare the forward pass run times of our ICG approximation process, signal processing pipeline (ICG u -NN) and the GCN [30] architecture. We sample graphs of sizes up to 7,000 from a dense and a sparse Erdős-Rényi distribution ER(n, p(n) = 0.5) and ER(n, p(n) = 50 n ), correspondingly. Node features are independently drawn from U [0, 1] and the initial feature dimension is 128. ICG u -NN and GCN use a hidden dimension of 128, 3 layers and an output dimension of 5. Results. Figure 6 demonstrates a strong linear relationship between the runtime of our ICG approximation and that of the message-passing 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 its overall time complexity. Additionally, Appendix F.7 reveals a strong square root relationship between the runtime of ICG u -NN and the runtime of GCN for both sparse and dense graphs. This aligns with our expectations, as the time complexity of GCN is O(E), while the time complexity of ICG-NNs is O(N ), highlighting the computational advantage of using ICGs over message-passing neural networks.Setup. We measured the average time until convergence in seconds for the GCN and ICG u -NN architectures on the non-sparse graphs tolokers [43] , squirrel [45] and twitch-gamers [36] . We follow the 10 data splits of Platonov et 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. [34] for twitch-gamers. We ended the training after 50 epochs in which the validation metric did not improve. We set the hyper-parameters with best validation results.Results. Table 6 shows that ICG u -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 in efficiency.In this subsection, we compare the memory allocated during the ICG approximation process and during a forward pass of the GCN [30] architecture. We sample graphs of sizes up to 2,000 from a dense Erdős-Rényi distribution ER(n, p(n) = 0.5). Node features are independently drawn from U [0, 1] and the initial feature dimension is 128. ICG u -NN and GCN use a hidden dimension of 128, 3 layers and an output dimension of 5. Results. Appendix F.9 demonstrates a 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 O(ED), and of ICG-NNs O(EK + N KD), where D is the feature dimension and K is the number of communities used for the ICG approximation.Latent graph GNNs. One way to interpret our 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, or from some raw non-graph data. Two motivations for latent graph methods are (1) the given graph is 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.Some examples of latent graph methods are papers like [31, 57, 16, 10, 17] which learn a latent graph from non-graph raw data. Papers like [39, 59, 28, 21] treat the given graph as noisy or partially observed, and learn the "clean" graph. Papers like [54, 50] modify the given graph to improve the efficiency of message passing (e.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, 52, 64] , can be interpreted as latent graph approaches.The statistics of the real-world node-classification, spatio-temporal and graph coarsening benchmarks used can be found in Tables 7 to 9 . In Tables 10 to 12 , we report the hyper-parameters used in our real-world node-classification, spatiotemporal and graph coarsening benchmarks. For spatio-temporal dataset, we follow the methodology described in [15] , where the time of the day and the one-hot encoding of the day of the week are used as additional features.Justification: We discuss the model's limitations in the conclusions section. Primarily, our approach is constrained to the single, 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 no 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 a 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: We use a single NVidia L40 GPU (with a 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 not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: The paper proposes a general purpose computational pipeline for efficient learning on large non-sparse graphs, focusing mainly on theoretical/mathematical 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.Guidelines:• The answer NA means that there is 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 or 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 a 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 disinformation. 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.• 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 or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper does not pose such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: 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? Answer: [Yes] Justification: We cite the owners of each dataset and state the version and splits that are used in Section 6.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] 38th Conference on Neural Information Processing Systems (NeurIPS 2024).[20] proposed an algorithm for finding the ICG, but it has impractical exponential runtime (seeSection 7).The definition of cut metric involves maximization, so minimizing cut metric is an unstable min-max.Note that the optimal Frobenius error is not uniformly small, since adjacency matrices of simple graphs are {0, 1}-valued, typically very granular, so they cannot be approximated well by low-rank R-valued ICG matrices. Nevertheless, if we find an approximate Frobenius minimizer, we are guaranteed a small cut metric error.We convert the result of[2] to our notations and definitions.Two sets of nodes (parts) U, V ∈ [N ] with connections between the parts but not within the parts can be represented by the ICG (1U∪V 1 ⊤ U ∪V -1U1 ⊤ U -1V1 ⊤ V ).We either ignore the signal in the loss, or concatenate random training signals and reduce their dimension to obtain one signal with low dimension D. This signal is used as the target for the ICG.All our experiments are run on a single NVidia L40 GPU. We made our codebase available online: https://github.com/benfinkelshtein/ICGNN.In the definition of W A , the convention is that ⌈0⌉ = 1. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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)$. 
This 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.

2. 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. 

     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.

      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.

3. 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.

4. Their theory (Theorem 3.1) only works for very large K values for reasonably sparse graphs that can be seen in most datasets.
questions: 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.

2. 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?

[1] Ying, Zhitao, et al. "Hierarchical graph representation learning with differentiable pooling." Advances in neural information processing systems 31 (2018).
limitations: 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).
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- There are a few minor mistakes. For example, could (14) on line 110 be a mistake for (4)?
questions: 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: limitations: If there is no simple way to determine the applicability of the proposed method, it may limit the range of its practical application.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
  - Hierarchical Inter-Message Passing for Learning on Molecular Graphs (ICML workshop 2020)
  - Scaling Up Graph Neural Networks Via Graph Coarsening (KDD 2021)
  - GRAPH CONDENSATION FOR GRAPH NEURAL NETWORKS (ICLR 2022)
  - A Provable Framework of Learning Graph Embeddings via Summarization (AAAI 2023)
  - Gapformer: Graph transformer with graph pooling for node classification (IJCAI 2023)
  - Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data (NeurIPS 2023)
  - Fast Graph Condensation with Structure-based Neural Tangent Kernel (WWW 2024)
  - Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning (ICML 2024)
- 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?
- 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.
- 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)?
questions: 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.
- 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. 
- Notations: How about using more distinguishable notations for node features S and signals \italic{S}? This might not be clear to readers.
limitations: limitations: The authors adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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.

3. 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.


4. To demonstrate the efficacy of the proposed initialization method, the paper should include a comparison with existing initialization methods, such as random initialization.
questions: 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: limitations: N/A.

Comments: comment: > I acknowledged the author's response. Thank you for the detailed explanations and they resolved my concerns. I will raise my score.

We warmly thank the reviewer for acknowledging our rebuttal and raising their score.

> Please include our discussions on your camera-ready paper. Looking forward to seeing the revised paper!

We will make sure to include all of the valuable points that the reviewers mentioned during the rebuttal in the final version of our paper.

We would like to thank the reviewer again.
> Thank you for your thorough response. Additionally, the supplementary experiments with real data have demonstrated the validity of your approach.

We thank the reviewer for acknowledging our rebuttal and participating in the discussion period.

> My concerns appear to be largely resolved by the more precise mathematical descriptions you provided.

We are glad to have resolved the reviewer's concerns. If the reviewer now sees the paper as worthy of publication, we hope they can increase their score above the threshold of acceptance to reflect that. We would like to use this opportunity to clarify remaining concerns that might prevent the a higher score.

Regardless, we would like to warmly thank the reviewer again.
I acknowledged the author's response. Thank you for the detailed explanations and they resolved my concerns. I will raise my score.

Please include our discussions on your camera-ready paper. Looking forward to seeing the revised paper!
Thank you for your thorough response. My concerns appear to be largely resolved by the more precise mathematical descriptions you provided. Additionally, the supplementary experiments with real data have demonstrated the validity of your approach. Therefore, I will keep my rating unchanged.

Thank you again.
We thank the reviewer for their comments and for acknowledging our work’s theoretical novelty and its future work potential. Since the author-reviewer discussion period is closing soon, we would highly appreciate feedback on our response. We are keen to take advantage of the author-reviewer discussion period to clarify any additional concerns.
> In general, the paper contributes insights to the field

We thank the reviewer for acknowledging the contribution of this work to the field.

> there are still areas for improvement, such as further validation to ensure the robustness and scalability of the model.

To further validate and ensure the robustness and scalability of our model, we conducted additional experiments which were not previously mentioned in our rebuttal to your review, testing ICG-NNs and their subgraph variation:
* **Comparison to graph coarsening methods** - 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** - 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.

> I thank the authors for their rebuttal, which partially addresses my concerns.

We would like to use this opportunity to clarify remaining concerns. Could you give us specific issues you are concerned with, so we have the opportunity to address them?


In light of this we would greatly appreciate a reconsideration of the current score.
> Most of my concerns have been addressed, so I want to raise my score to 6.

We warmly thank the reviewer for acknowledging our rebuttal and raising their score.
> I would like to encourage the authors to keep revising their paper as some parts are hard to follow in the current version and to update their manuscript with their rebuttal experiments and potentially more new datasets.

We will make sure to include all of the  points that were mentioned during the rebuttal in the final version of our paper.
> It should be near 500 if you are using the original one, or near 100 if you are using the GraphSAINT version (according to the PyTorch Geometric library website).

Thank you for pointing this out. You are correct, reddit's average degree is 491.99.
I thank the authors for their rebuttal and new experiments.

> While standard benchmarks of large graphs are quite sparse, 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 ...

Thanks this has been an insightful response. I also think that the focus of most of the methods on large graphs has been on the sparse graphs and there is not enough work on denser graphs. I would also suggest adding this argument to your work and encouraging the community to work more on the denser, real-world graphs. 

**New experiments**: Thank you for running new experiments; the results are more convincing now. Just for the Reddit dataset, the average degree mentioned does not seem correct. It should be near 500 if you are using the original one, or near 100 if you are using the GraphSAINT version (according to the PyTorch Geometric library website). Also, ogbn-proteins can be a good candidate as it has a high average degree of near 600.

**New Theory**: Thank you for updating; this is a more reasonable bound now.

In general, I would like to encourage the authors to keep revising their paper as some parts are hard to follow in the current version and to update their manuscript with their rebuttal experiments and potentially more new datasets. Most of my concerns have been addressed, so I want to raise my score to 6.
I thank the authors for their rebuttal, which partially addresses my concerns. In general, the paper contributes insights to the field, but there are still areas for improvement, such as further validation to ensure the robustness and scalability of the model. As a result, I will maintain my current score.