Spectral Greedy Coresets for Graph Neural Networks

This paper aims to apply the coreset method, for efficiently processing large data sets, to node classification by considering spectral embeddings of (diffusion ego nets). As the authors note, ego nets are similar to the receptive field used in standard Message Passing GNNs. And they also claim that spectral embeddings of ego nets are a smooth node feature. (They prove this in the case where the node features are iid Gaussians, which is NOT convincing)

This paper contributes with a novel approach to select training nodes in a very large graph, where the processing of all of them via GNNs leads to OOM (Out-of-memory). This problem is known as "coreset selection" in the literature. The typical setting is to learn non-negative weights leading to minimize the deviation between the "as per node loss" and the training loss (empirical risk): zero weight means that the training node is not informative for learning. This is consistent with the "locality principle" of GNNs where node embeddings mostly rely on those of their neighbors. The authors leverage this principle by building quasi-independent node samples: aking subgraphs around training nodes and considering only the features of the nodes in each subgraph. In particular, they propose to limit the subgraphs to ego-graphs (close nodes, e.g. shortest path).

The main contribution of the paper is as follows. The authors formulate the coreset selection problems in terms of finding local embeddings close to real ones (under the assumption that the error of this approximation is bounded). This is explained via the spectral domain of the embedding, and this leads in turn to minimize an upper bound which is independent of the spectral embeddings themselves: it depends on the diffusion (transition) matrix P. The minimization is done by a variant of the greedy geodesic iterative ascent (GIGA) algorithm.

The proposed algorithm is proven to outperform with other coreset selection algorithms, but in mid-sized such as Flicker. It is also tested with very large graph where its greedy nature provides efficiency wrt the alternatives.

In this paper, the authors aim to solve the computational efficiency problem of GNN by proposing a coreset selection algorithm for GNN in node classification tasks. The proposed method named spectral greedy graph coresets(SGGC) is a two steps greedy algorithm: 1) it first find a large set of ego-graphs that are distance from each other to cover the topology information of graph as much as possible, 2) then it filter out subgraphs that are not contributing to optimization of the classification loss. This “extrapolate” and “exploit” approach effective compress the size of training data without pre-training while maintaining the downstream GNN performance in node classification. The authors provided both theoretical guarantee and extensive experimental validation on multiple large datasets. The method works well with different GNN structure and doesn’t require any pre-training or repetitive inference, which improves it efficiency and generalization capability.

This work introduces a coreset (subgraph) selection method (SGGC) for graph neural networks (GNNs) to substantially accelerate the training process. The key idea is to identify the most relevant subgraph (e.g. the depth-L ego-graph) by leveraging the spectral embedding vectors of neighboring nodes. A theoretical analysis of the error bound for node classification loss has been provided.

This paper proposes a coreset selection procedure for GNN training (focusing on node classification tasks). In order to avoid node-dependence issues, as is typical, the authors look at ego-nets and pick the entire neighborhood at once. They then transform the search problem into the spectral space, which makes it easier to use submodular optimization (and greedy algorithm) and avoid redundancy. The intuition is that far-away nodes are less redundant (hence prior work based on k-means and k-center for coreset construction). Unlike previous work on graph condensation, this work looks at multiple hops in the ego-net, which reduces the "complexity" of the optimization problem by introducing a smoothness condition. This relies on the typical assumption that GNN essentially computes a "local" function. The multi-hop ego-net, though, adds to the size of the data, which the authors claim can be reduced by PCA.

Motivated by the scalability challenge of training large GNN models, this paper studies the problem coreset selection for GNNs. More concretely, the authors define the coreset for GNN as a subset of labeled nodes, and the goal is to select a small coreset so that if we train the model with the loss computed only on the coreset, the testing accuracy should be similar to training on the full labeled set. The authors cast this as an optimization problem. The problem is intractable so the author simplifies the problem significantly according to some observations and assumptions. Then using existing techniques to obtain the coreset. In the experiments, the proposed coreset framework exhibits certain advantages over other graph reduction techniques for training GNNs.

This paper proposes a novel graph coreset method, called Spectral Greedy Graph Coresets (SGGC), to accelerate the training of graph neural networks (GNNs) by using less training data. SGGC adopts a two-stage training strategy: It first coarsely selects the widely spread ego graphs and then refines the selections by considering the diversity of its topology. A greedy algorithm is proposed to approximate these two training objectives. Extensive experiments validate the effectiveness of the proposed method over various graph reduction methods, including sampling, coarsening, and condensation.

The paper introduces a new method for speeding up the training of GNN. The main idea behind the paper is to build a coreset by identifying important subgraphs via spectral embeddings.

The paper contains some interesting ideas but some important limitations have been highlighted during the review process:

• the experimental results on large graphs are not too convincing

• the computation complexity of the method is a bit problematic

• the theoretical analysis relies on untested assumptions

Overall, the paper has some merits but it is below the acceptance bar of ICLR.

Reject