Scalable Graph Coreset Selection via Greedy Sampling

Average Distance Approximation for Static Large Graphs

Calculating average distances in large-scale networks is computationally intensive and constrained by limited main memory, posing a significant challenge in graph analytics. This study explores and evaluates two primary approaches for estimating average distances: a graph sampling-based method (Random Walk) and landmark-based methods, including the Size Estimation Framework (SEF) and the Eppstein-Wang (EW) algorithm. Random Walk was found to be unreliable for small sample sizes and computationally expensive for larger ones, requiring at least 15% of nodes for accuracy. Landmark-based approaches, leveraging probabilistic data structures like HyperLogLog for memory-efficient neighbor exploration, demonstrated superior performance. Among these, the SEF algorithm offers better memory efficiency, while the EW algorithm achieves higher accuracy with lower computation time. Experiments on static, undirected, and unweighted graphs (both unipartite and bipartite) revealed that the EW algorithm produced results with an error margin as low as 0.02%. Additionally, a subset of 100 randomly selected nodes was sufficient for accurate estimations in most large graphs. The findings indicate that the EW algorithm provides a practical and scalable solution for average distance estimation, with higher reliability on unipartite graphs compared to bipartite graphs.

Scalable Algorithms for Information Centrality Optimization via Global Edge Addition

Information centrality is a powerful metric for quantifying node importance and has demonstrated practical value in a variety of real-world applications. Although existing studies have explored information centrality optimization via edge addition, they are restricted to a local setting, where candidate edges must be incident to the target node. Such restrictions fail to fully exploit the global structure of the network and often lead to suboptimal solutions under the same edge budget. In this work, we study the problem of global information centrality optimization, where candidate edges may connect any pair of currently non-adjacent nodes. This formulation significantly enlarges the search space and breaks the supermodularity property that underlies traditional greedy approaches, making the problem substantially more challenging. To address these challenges, we propose two scalable greedy algorithms based on gradient-guided edge selection. Our methods exploit geometric interpretations, dimensionality reduction techniques, and nearly-linear-time Laplacian solvers to efficiently approximate marginal gains and prune the candidate edge set. Extensive experiments on real-world networks demonstrate that our algorithms achieve optimization performance comparable to exact greedy strategies while substantially reducing computational time.

HP-MC: Quickly Computing Maximum Clique Sizes of Large Sparse Graphs

Parallel Spectral Graph Sparsification via Low Diameter Decompositions

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.

Efficient Coreset Selection via K-Nearest Neighbor Graphs

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.

Distributed Maximal Independent Set Computation in Hundred Billion-Edge Graphs

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.