Learning on Large Graphs using Intersecting Communities

We thank the reviewer for their comments and for acknowledging the theoretical significance of our constructive version of the Weak Graph Regularity Lemma. We address each of their questions/concerns below.

W1: The proposed method's speed advantage over MPNNs hinges on the assumption that the chosen number of communities K should be less than the node degree (line 170)...

Answer: Thanks for raising this point, this was an oversight. We conducted further experiments with a significantly lower number of communities $K=50$, achieving an accuracy of 66.08 ± 0.74 and 65.27 ± 0.82 for $\text{ICG}_u-\text{NN}$ and ICG-NN, correspondingly. Thus achieving state-of-the-art results while retaining the speed benefits of ICG-NN.

W2: The computation of the ICG requires an offline pre-computation step that, while only performed once, involves a time complexity linear to the number of edges.

Answer: That is accurate. The time complexity of the ICG fitting process is similar to the time complexity of MPNNs, linear in the number of edges. Let us clarify that this is a strength of ICG-NNs. The ICG fitting process is only done once and does not require extensive hyperparameter optimization and architecture tuning, unlike MPNNS. Thus, ICG-NN offer a potentially significant advantage over standard MPNNs. This gap between ICG-NNs and MPNNs is further amplified for time series on graphs.

W3: In the Runtime Analysis section, the authors should also include a time comparison for the model's convergence, in addition to the per-epoch runtime.

Answer: Based on the reviewers' suggestion, we measured the time (in seconds) until convergence for the GCN and $\text{ICG}_u-\text{NN}$ architectures across the node-classification tasks presented in Appendix F.1, Table 2. We ended the training after 50 epochs in which the validation metric didn’t improve. We set the hyper-parameters with best validation results. The results are shown in the following table:

It is clear that $\text{ICG}_u-\text{NN}$ consistently converges faster than GCN across all three benchmarks. Specifically, $\text{ICG}_u-\text{NN}$ converges approximately 15 times faster on the tolokers dataset, 17 times faster on the squirrel dataset, and 25 times faster on the twitch-gamers dataset compared to GCN, indicating a significant improvement in efficiency. We will add this to the revised paper.

W4: To demonstrate the efficacy of the proposed initialization method, the paper should include a comparison with existing initialization methods, such as random initialization.

Answer: We repeated the node classification experiments presented in Table 2, as described in Appendix F.1, using random initialization when optimizing the ICG, and compared the results to those obtained with eigenvector initialization.

The results indicate that eigenvector initialization generally outperforms random initialization across all datasets. While the improvements are minimal in some cases, such as with the tolokers and squirrel datasets, they are more pronounced in the twitch-gamers dataset.

Additionally, eigenvector initialization offers a practical advantage in terms of training efficiency. On average, achieving the same loss value requires 5% more time when using random initialization compared to eigenvector initialization. This efficiency gain further supports the utility of the proposed initialization method.

We will add these results and discussion to an ablation study section in the appendix.

Q1: Has the author evaluated the relationship between the model's performance and the cut-metric...

Answer: Figure 4 in Appendix F.2 shows the relationship between test accuracy and the number of communities used, while Figure 5 in Appendix F.3 illustrates the relationship between cut-norm, Frobenius norm, and the number of communities. Using these figures, we present the accuracy as a function of the cut-norm, as requested by the reviewer:

We observe that as the cut-norm error increases, the test accuracy generally decreases. This indicates that a lower cut-norm, which corresponds to a more refined community structure, tends to result in higher accuracy of the model, as expected.

it is important to question whether this assumption holds in ther contexts, such as molecular graphs

The setting in this paper is a single large graph. Our setting does not extend to a dataset of many graphs. Molecular graphs are typically used in graph classification or regression, which is not appropriate for our method. This is emphasised in Line 44.

We thank the reviewer for their comments and for finding our work theoretically significant.

W1: ICG+GNN is similar to summarizin…

Answer: In Comparison of ICG-NN to graph coarsening in the common response, we highlight the main differences to pooling methods.

… The examples of recent papers are stated below…

Answer: We agree, and for that reason we mentioned intersecting communities, stochastic block models and GNNs with local pooling in our related work sections: Section 7 and Appendix I.

Let us highlight the fundamental differences between the mentioned papers and ours:

1. Computational complexity - Condensation methods require $O(EM)$ operations to construct a smaller graph [3,6,7,8], where $E$ is the number of edges of the original graph and $M$ is the number of nodes of the condensed graph. Conversely, we estimate the ICG with $O(E)$ operations.
2. Graph construction - Methods like coarsening [1,2], condensation [3] and summarization [4], typically rely on heuristics. In contrast, ICGs provide a provable approximation of the original graph.
3. Handling graphs that do not fit in memory - ICG-NNs offer a subgraph sampling approach when the original graph cannot fit in memory. In contrast, the aforementioned methods lack a strategy for managing smaller data structures when computing the compressed graph.

In line with the reviewer's suggestion, we will include the proposed references with an appropriate discussion.

In addition, we provide an empirical comparison in Table 1 of rebuttal.pdf between our method and the aforementioned approaches on the reddit and flickr datasets. ICG-NNs achieve state-of-the-art performance.

W2: The time and memory required for real runtime to fit ICGs…

Answer: In Appendix F.4 we compare the forward pass run times of our ICG approximation process, signal processing pipeline ($\text{ICG}_u-\text{NN}$) and the GCN architecture, demonstrating a linear relationship between the two.

Following your request, we estimated the GPU memory used while fitting an ICG. We follow a similar setup to the run time experiments, with Erdos-Rényi graphs with 128-dimensional node features sampled from $U[0,1]$. Both $\text{ICG}_u-\text{NN}$ and GCN use a hidden dimension of 128, 3 layers and an output dimension of 5:

Figure 1 in rebuttal.pdf reveals a linear relationship between the memory allocated for $\text{ICG}_u-\text{NN}$ and for GCN. This aligns with our expectations: the memory complexity of GCN is $O(Ed)$, and of ICG-NNs $O(EK)$.

W3: Evaluation across datasets...

W4: …there are many more single, large, undirected graph...

Is the largest dataset used in the experiment large enough…

Answer: We conducted additional experiments using the reddit and flickr datasets, which are significantly larger than the datasets used in our initial submission. We provide an empirical comparison in Table 1 of rebuttal.pdf between our method and existing efficient approaches. ICG-NNs achieve state-of-the-art performance, further solidifying its effectiveness.

Our method is designed for large and non-sparse graphs. Unfortunately, very few datasets meet this criterion. Standard benchmarks of large graphs are quite sparse. However, in applications in the industry, one often has to work with large and not very sparse graphs. Remarkably, ICG-NN still performs very well on the available sparse large graphs. In the paragraph in line 173, we explain how ICGs are still often meaningful for sparse graphs in practice. See Choice of datasets in the common response for more details.

Plus, is this method superior to existing scalable GNNs…

Answer: We measured the time until convergence for the GCN and $\text{ICG}_u-\text{NN}$ architectures and tasks presented in Appendix F.1, Table 2. We ended the training after 50 epochs in which the validation metric didn’t improve. We set the hyper-parameters with best validation results. The results:

$\text{ICG}_u-\text{NN}$ consistently converges faster than GCN across all three benchmarks. We will add this to the revised paper.

Q1: p 249: Why does the operation on Community feature vector $F$ is $O\left(K^2D^2\right)$...

Answer: When defining the general MLP, $F$ is flattened into a $KD$ dimensional vector. A linear operator hence requires $KD \times KD$ parameters. We will clarify this in the text.

Q2: $p$ 253: Why is $Q^\dagger Q$ an identity…

Answer: If $Q$ is full rank at initialization (which is true almost surely for random initialization), and if $A$ is not low rank, then the optimal configuration of $Q$ is full rank. The optimization would not benefit from having multiple instances of the same community. This would be equivalent to reducing the number of communities from $K$ to $K-1$. We will clarify this in the paper.

Q3: How about using more distinguishable notations...

Answer: We follow the standard numerical linear algebra notation, where $\mathbf{s}_i$ denotes the i-th row/column of the matrix $\mathbf{S}$ and it is standard to use the same letter for both.

[1] Hierarchical Inter-Message Passing for Learning on Molecular Graphs, 2020.
[2] Scaling Up Graph Neural Networks Via Graph Coarsening, 2021.
[3] Graph Condensation for Graph Neural Networks, 2022.
[4] A Provable Framework of Learning Graph Embeddings via Summarization, 2023.
[5] Gapformer: Graph Transformer with Graph Pooling for Node Classifcation, 2023.
[6] Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data, 2023.
[7] Fast Graph Condensation with Structure-based Neural Tangent Kernel, 2024.
[8] Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning, 2024.

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.

We thank the reviewer for their comments and for highlighting the novelty of our approach and the overall quality of the paper. We address each of their questions/concerns below.

W1: …it is necessary to have a straightforward way to determine how dense a graph needs to be for the proposed method to be effective, or under what conditions of sparsity it remains effective…

Q1: Is there a straightforward way to determine how dense a graph needs to be for the proposed method to be effective…

L1: If there is no simple way to determine the applicability of the proposed method, it may limit the range of its practical application.

Answer: We first note that after submitting the paper, we managed to significantly improve the asymptotics, which requires only a minor revision to the proof. The multiplicative constunt in (6) is now $3N/2\sqrt{E}$ instead of $3N^2/2E$. Moreover, we show that this asymptotic is essentially tight. Namely, there are graphs for which there does not exist any ICG that approximates them with an error less than $O(N/\sqrt{KE})$. This can be read from Theorem 1.2 in [1] (when converting their result to our definitions and notations). While this response is too short to show the proof, we are happy to send an anonymous PDF with the proof to the AC according to the rules and regulations of NerIPS, so you can verify it. This improved theorem leads to a better comparison to MPNN methods. Now, ICG requires $K>N^2/E$ to guarantee that ICG approximates any given graph. For example, for a graph with $10^5$ nodes and average node degree $800$, one needs $K=125$ communities.

This bound is still pessimistic for sparse graphs. As written in the paragraph in Line 173, we note that in practice, ICGs approximate also sparse graphs well under relevant structural assumptions. In the spare case where $K<N^2/E$, the theory only motivates the engineering, but does not guarantee a quantitive approximation bound for all lgraphs. In this case, we will write the following rule of thumb in the revised paper, which we actually observed and used in practice:

"We observe in practice that when the relative Frobenius error between the graph and the ICG is less than 0.8, the cut norm error is usually small."

Note that the Frobenius error is cheap to compute, and it is computed anyway as part of the optimization, while the cut norm, which is the actual theoretical target, is expensive to estimate.

We will add this certificate to all of the tables in the paper.

W2: There are a few minor mistakes. For example, could (14) on line 110 be a mistake for (4)?

Answer: Thank you for pointing that out. We will correct this error, along with any other minor typos.

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

W1: Their analysis on the time complexity…

L1: The method seems to be more efficient for very dense graphs…

Answer: A general message passing layer applies a function on the concatenated pair of node features of each edge. We refer to this general formulation of MPNN, which takes $O(ED^2)$ operations for MLP message functions.

The reviewer is correct that in some simplified message passing layers (e.g., GCN and GIN) the message is computed using just the feature of the transmitting node. Here, the complexity is reduced to $O(ED+ND^2)$. We will add this special case to the paper and compare asymptotics to ICGNN.

Even for such simplified GNNs, for graphs with large average degree (the graphs of interest in our paper), taking $K$ less than $d$ makes sense. While standard benchmarks of large graphs are quite sparse (tolokers, $d=88$, squirrel $40$, reddit $50$), we believe that this is a result of the research community focusing on sparse graphs when developing methods for large graphs. However, in industrial applications, one often has to work with large and not very sparse graphs. See examples under Choice of datasets in the common response. For lack of such large and relatively dense publically available graphs, we have to make do with the available sparse large graphs, where our method performs remarkably well nevertheless. We hope the reviewer would agree that the lack of available high quality benchmarks should not be a reason to reject our contribution.

Lastly, while taking $K=d$ may seem to give the same efficiency for GCN and ICG-NN, an ICG-NN has the advantage that it works with a regular array of a fixed dimens as the data structure. In contrast, GCN has to move between two data structures - the list of edges and the list of node features. This is less efficient in practice.

W2: The paper gets unnecessarily complex…

Starting in Section 3.1, the use of $C$ and $P$ for finding…

Answer: We are happy to improve our notations in the revised paper.

The matrix norms in our paper are not used on (non-negative) adjacency matrices but on (real-valued) differences between adjacency matrices. The distinction is critical. The cut norm of an adjacency matrix is just its L1 norm, but the cut norm of a general matrix is not. Thus, using the adjacency matrix $A$ to denote the variable inside the cut norm would be an abuse of notation. We will clarify this in the revised paper.

We cannot replace the notation $P$ by $F$, since they are related by $P=QF$. We will change $b$ in (5) to $f$ to be consistent with the relation between $P$ and $F$. We will also change the generic matrix notation in Definition 2.1 to $M$.

Definition 3.1 defines $\mathcal{Q}$ as a set of functions...

Answer: Definition 3.1. introduces rigorously the soft affiliation model $\mathcal{Q}$, which is a set of functions $q:[N] \rightarrow \mathbb{R}$. Given a soft affiliation model $\mathcal{Q}$, Definition 3.2. rigorously introduces the soft rank-1 intersecting community graph model $[\mathcal{Q}]$.

We are happy for the opportunity to improve the wording and make the definition clearer. We will start Definition 3.2 with:

"Let $d\in\mathbb{N}$, and let $\mathcal{Q}$ be a soft affiliation model. We define $[\mathcal{Q}]\subset\mathbb{R}^{N\times N}\times \mathbb{R}^{N\times D}$ to be the set of all elements..."

W3: While the main point is the efficiency of the method, the results for node classification...

Answer: We conducted additional experiments using the flickr dataset, which is significantly larger than the datasets used in our initial submission. Our IGCNN with subgraph ICGm with 1% sampling rate, achieves competitive performance with competing methods that operate on the full graph.

W4: Their theory (Theorem 3.1) only works for very large K…

Answer: We managed to significantly improve the asymptotics, which requires only a minor revision to the proof. The multiplicative constant in (6) is now $3N/2\sqrt{E}$ instead of $3N^2/2E$. Moreover, we show that this asymptotic is essentially tight. Now, ICG requires $K>N^2/E$ to guarantee that ICG approximates any given graph. See Improved asymptotic analysis under the common response for more details.

On the other hand, as written in the paragraph in Line 173, in practice, ICGs approximate also sparse graphs well. In the spare case the theory only motivates a class of graphs on which the computational method works, but does not guarantee a quantitative bound. This approach to motivating computational methods from theory is very common and accepted by the research community.

Q1: Is there any time measured for fitting an ICG…

Answer: Run time analysis which shows a linear relationship between the runtime of ICG approximation and GCN be found in Appendix F.4, lines 1191-1194. The reduction in hyperparameter tuning is mentioned to motivate the usage of ICGs instead of MPNNs in Section 8, lines 381-382. We will highlight these points further in the final version.

Q2: What is the relation of your work to graph coarsening...

Answer: In Comparison of ICG-NN to graph coarsening in the common response, we highlight the main differences. The summary is:

1. Coarsening methods do not have theoretical guarantees. ICGs provably approximate the graph.
2. Pooling methods do not asymptotically improve run-time. ICG-NNs do.
3. Pooling methods are MPNNs. ICG-NN is not interpreted as message passing.
4. Graph coarsening process representations on an iteratively coarsened graph. ICG-NNs process the fine information at every layer.