TopoBudget couples exact multiscale connectivity with budgeted, reusable community preservation, and proves exact preservation of the component partition at every threshold, and that the conditioned objective is monotone and submodular, so greedy attains a (1-1/e) guarantee for the fixed-backbone residual problem.
Abstract
Web and social graphs are analyzed repeatedly for community structure, yet many of their edges are redundant for this purpose, which motivates sparsification. Existing sparsifiers preserve spectral quantities, cuts, local similarity, or a single clustering, but none preserves the thresholded connectivity structure of an edge-relevance filtration, the multiscale pattern by which groups form at high relevance and merge through weaker bridges. We study persistent-connectivity-preserving sparsification: given a graph, an edge-relevance filtration, and a proxy partition computed once during preprocessing, select a budgeted subgraph that preserves the labeled component partition at every threshold, and hence the zero-dimensional persistence diagram, while retaining community evidence for later analyses. Our method, TopoBudget, first extracts a tie-aware persistence backbone that enforces this constraint, then allocates the residual edge budget by greedily maximizing a backbone-conditioned submodular objective that rewards balanced recovery of proxy-internal degree. We prove exact preservation of the component partition at every threshold, and that the conditioned objective is monotone and submodular, so greedy attains a (1-1/e) guarantee for the fixed-backbone residual problem. On held-out synthetic benchmarks and six real Web and social graphs at equal budget, TopoBudget gives the strongest community preservation among topology-preserving methods under Louvain, remains competitive under Infomap, incurs zero topology mismatch, and runs substantially faster than an effective-resistance baseline. A no-backbone ablation shows that, on the real graphs, the mandatory backbone improves average quality while providing the exact guarantee. TopoBudget thus couples exact multiscale connectivity with budgeted, reusable community preservation.
Force-Directed Placement (FDP) is a widely used approach for network visualization, yet scaling it to massive graphs while preserving clear community structures remains a major computational and visual challenge. Existing approximation methods often rely on auxiliary data structures (e.g., spatial trees), which introduce substantial memory overhead; furthermore, traditional power-function-based forces frequently fail to separate dense clusters effectively. In this paper, we present a negative sampling-based algorithm that achieves O(|E|) time complexity with a low memory footprint, without requiring complex multi-level representations. In a first step, we introduce a linearly normalized degree-weighting scheme, which, combined with short-range bounded $t$-distribution forces, effectively untangles dense structures and enhances visual cluster separation. To optimize for this formulation efficiently, we introduce an edge-centric negative sampling strategy that naturally reconstructs the global degree-weighted objective. Furthermore, we design a lock-free, bundle-based parallelization scheme that leverages the sparsity of stochastic updates to achieve significant speedups while mitigating access conflicts. Comprehensive evaluations on 12 large-scale graphs demonstrate that the proposed method outperforms state-of-the-art algorithms in neighborhood preservation and cluster separation. Compared to existing baselines, our method reduces memory consumption by 72% on average and leverages simple GPU parallelism to generate a high-quality layout for a graph with 4 million nodes and 34 million edges in below 10 seconds.
Xin Chen, Shuowei Hou, Yifan Wang et al.· 0 citations
We show that every weighted hypergraph on $n$ vertices admits a spectral $\varepsilon$-sparsifier with $O(n\log n/\varepsilon^2)$ hyperedges, strengthening the independent STOC 2023 works of Lee and Jambulapati--Liu--Sidford by removing their rank dependence and answering Lee's open question on whether this loss is inherent. The key idea is global-dictionary chaining: after choosing clique edge weights with balanced effective resistances, every hyperedge seminorm is Lipschitz with respect to the same global-dictionary norm generated by normalized vertex-pair directions; the local rank complexity is thereby replaced by the Gaussian width of this common dictionary. Since these STOC 2023 works have become standard analytic primitives across a broad subsequent literature on spectral hypergraph sparsification and its variants, our rank-independent theorem sharpens many later guarantees that inherit their sampling bounds.
Retrieving coherent evidence subgraphs is critical for Knowledge Base Question Answering (KBQA). Existing paradigms often treat facts independently, rely on biased heuristics, or employ myopic search, failing to optimize collective subgraph utility. In this paper, we propose COS-MOS ( C onnectivity-O riented S ubmodular M aximization for O ptimal S ubgraph Retrieval), a unified framework that formalizes evidence retrieval as a constrained submodular maximization problem. This formulation mathe-matically captures the trade-off between information relevance and structural complexity. To tractably solve this combinatorial challenge, COSMOS employs a decompose-and-conquer strategy, which first performs a seed-guided greedy expansion to maximize local semantic utility, followed by a topology-aware component aggregation to bridge disjoint evidence clusters via Maximum Spanning Tree aggregation. Guided by theoretical bounds, we introduce Structure-Aware Contrastive Tuning to align semantic space with KG topology. Experimental results on WebQSP, CWQ, and M 3 GQA benchmarks demonstrate that COS-MOS achieves state-of-the-art performance.
Boci Peng, Xiao Liu, Boren Hu et al.· Annual Meeting of the Associ...· 0 citations
Community search is a fundamental graph-based retrieval problem that aims to identify a query-dependent subgraph whose nodes exhibit strong internal connectivity. While recent learning-based methods improve retrieval effectiveness via graph representation learning, they follow a ''one-use-one-train'' paradigm that requires retraining or fine-tuning for each target graph, leading to high data dependency, high training costs, and limited generalization. To handle this, we propose OFA-CS, a ''one-for-all'' community search framework trained once on source datasets and directly deployed to arbitrary unseen graphs without retraining or fine-tuning, while preserving strong performance. Specifically, we introduce a Spectral-Aware Feature Alignment module to unify feature dimensionality and align cross-domain semantics in a community-aware manner. We further develop a Graph Diffusion Tokenized Transformer that constructs hybrid token sequences from local and global structural contexts for Transformer encoding, and applies diffusion-based refinement to mitigate distribution shifts on unseen graphs. With the unified representations, communities are efficiently retrieved via a modularity-driven search procedure. Extensive experiments on diverse real-world graphs demonstrate that OFA-CS achieves strong cross-domain generalization and competitive retrieval effectiveness against state-of-the-art methods, without requiring target-domain supervision.
Mo Li, Zhaosong Zhao, Linlin Ding et al.· Annual International ACM SIG...· 0 citations
Unsupervised graph clustering is a fundamental technique for uncovering underlying semantic patterns in large-scale networks. Although Graph Contrastive Learning has demonstrated promising performance, existing methods often suffer from the"structural isolation"issue during mini-batch training, making it challenging to capture cohesive community structures that characterize the global topological distribution. To address these challenges, we propose SCISE, a Scalable unsupervised graph Clustering framework that preserves structural Integrity by synergizing community-aware sampling with constrained Structural Entropy. Specifically, we first introduce the Structural Entropy Community Constraint operator (SECC), which optimizes structural information within a constrained solution space to mitigate community fragmentation and enhance partition cohesion. Second, to prevent global information loss during batch training, we design a Community-Aware Sampling Expansion (CSampE) mechanism that incorporates the community context of target nodes into sampling batches, effectively breaking structural barriers and preserving topological integrity. Finally, we devise a Structural Contrastive Learning (StructCL) module that refines edge weights based on intra-batch structural similarity, guiding the encoder to learn representations in a higher-order structural space. Extensive experiments on six mainstream benchmark datasets demonstrate that SCISE significantly outperforms state-of-the-art algorithms, with ablation studies and robustness analyses further validating its effectiveness and reliability for real-world large-scale graphs.
Jingyun Zhang, Hao Peng, Jianxin Li et al.· 0 citations
In many practical scenarios, vector retrieval is frequently coupled with keyword constraints, particularly under Any-Match semantics. Filtered Approximate Nearest Neighbor Search (Filtered ANNS) has emerged as a widely adopted solution. Within this domain, state-of-the-art methods often utilize graph-based indices that enforce constraints via runtime filtering on a monolithic graph. However, real-world label skew degrades this monolithic design: frequent labels waste computation on largely valid neighborhoods, while rare labels suffer from graph sparsity in locating limited candidates. To address this, we propose GAAF, a frequency-aware Graph Ensemble framework that decouples the handling of high- and low-frequency labels. GAAF partitions the dataset into specialized graphs: utilizing dedicated indexes for high-frequency labels to eliminate redundant comparisons, while consolidating the rest of the labels into shared graphs to restore connectivity. Leveraging the fine-grained control afforded by this ensemble, we introduce NUMA-aware data placement to minimize remote access, and Adaptive Inter-graph Pruning to bypass redundant traversals. Experiments on diverse datasets demonstrate that GAAF significantly outperforms state-of-the-art baselines.