This work proposes a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule, well-suited for large-scale graphs where the full Laplacian cannot be stored in memory.
Abstract
Sampling representative nodes from large graphs is fundamental to graph signal processing and network analysis, yet existing methods require access to the full graph Laplacian, making them impractical at scale. We propose a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule. At each iteration, the algorithm accesses only a small random subset of Laplacian columns, requiring no eigendecomposition or global graph traversal, making it well-suited for large-scale graphs where the full Laplacian cannot be stored in memory. We analyze the algorithm under the stochastic block model and show that, when the degree distribution is balanced across nodes, the algorithm achieves sampling proportional to cluster size, and that the resulting mean estimate is controlled for band-limited graph signals in the Paley-Wiener space, with the error decaying as inter-cluster connectivity weakens. Numerical experiments on both synthetic and real-world data validate the effectiveness of the proposed method.
The findings indicate that the Eppstein-Wang algorithm provides a practical and scalable solution for average distance estimation, with higher reliability on unipartite graphs compared to bipartite graphs.
This work proposes two scalable greedy algorithms based on gradient-guided edge selection that efficiently approximate marginal gains and prune the candidate edge set and achieves optimization performance comparable to exact greedy strategies while substantially reducing computational time.
Runze Zhang, Gengyu Wang, Zhongzhi Zhang· Proceedings of the 32nd ACM...· 0 citations
We present a new solver-free parallel spectral sparsification algorithm for weighted graphs that relies only on parallel low-diameter decompositions and independent sampling. This yields the first algorithmic improvement over prior, solver-free parallel sparsification approaches since Koutis (2014) and, for the first time for a practical algorithm, eliminates any dependence on the target approximation accuracy ε in the algorithm's work and depth. Our algorithm works by sub-sampling edges according to their robust connectivity, as introduced by Kapralov and Panigrahy (2012). We show how to estimate the robust connectivities of G in an extremely simple manner: we create multiple random sub graphs Gp, where each edge in G is sub-sampled independently with probability pe = min {we · p, 1}. Then, we run a Low Diameter Decomposition in each of the graphs. If u and v often share a cluster in the LDDs, then this provides us with an upper bound on the robust connectivity of the edge e = (u,v). Carefully invoking this procedure for O (log n) different values of the probabilities p then allows us to obtain sufficiently good estimates for sub-sampling. We additionally complement the theory with an experimental evaluation demonstrating strong performance across relevant graphs and sparsity regimes.
Yves Baumann, Gernot Zöcklein· ACM Symposium on Parallelism...· 0 citations
Coreset selection reduces the cost of model training by replacing a large training set with a small representative subset. Existing gradient-approximation coreset methods such as CRAIG and cluster-based variants can preserve model accuracy. Still, their selection stages often rely on dense pairwise distances or large item-cluster bound matrices, leading to high time and memory costs on large datasets. This paper proposes KNNG-CS, a lightweight coreset selection method based on a $K$-nearest neighbor graph. KNNG-CS exploits local neighborhood structures to estimate the importance of each data item and greedily selects representative nodes without maintaining a quadratic distance matrix. The method requires only linear storage in the number of edges. Experiments on four real-world datasets show that KNNG-CS achieves accuracy comparable to representative gradient-approximation coreset methods, while reducing selection time by $2.3\times$-$41.2\times$ and peak memory to $0.3\%$-$7.5\%$ of the baselines.
Yingfan Liu, Leiyu Zhang, Jiadong Xie et al.· 0 citations
An independent set of an undirected graph is a subset of vertices where no two vertices included in the set are neighbors. A Maximal Independent Set (MIS) of a graph is an independent set such that no additional vertices can be added to the set without violating the requirements of an independent set. To support modern large graphs, parallel MIS algorithms and their multi-core, GPU, and distributed memory implementations have attracted widespread research interests in recent years. We present a distributed MIS solution to support applications that demand high throughput and scalability. Our solution is designed to support various randomized priority assignment techniques and to compute MIS in a fully asynchronous or round-synchronous manner, the latter is required by some priority assignment techniques. Our MPI-based prototype attains strong scaling by way of multilevel load-balanced graph partitioning, accelerates distributed processing through computationcommunication overlap and message prioritization, and produces deterministic results. We demonstrate scalability using massive datasets: e.g., a real-world web graph with 128 billion edges and 512 compute nodes (16 K CPU-cores), and competitiveness of our solution through empirical comparisons: our implementation comfortably outperforms both CombBLAS-MIS and AGM-MIS, and identifies MIS' of size comparable to those of the key parallel and distributed solutions found in the literature.
Yisheng Liu, Roger Pearce, Tahsin Reza· International Symposium on P...· 0 citations