Bipartite graphs are widely used in many real-world applications, where discovering clusters is crucial for understanding their underlying structure. However, most existing clustering methods for bipartite graphs enforce the assignment ofallvertices to clusters, often neglecting the important roles of outliers and hubs. To address this limitation, we plan to extend the structural clustering model from unipartite to bipartite graphs. This extension is non-trivial due to the lack of common neighbors in bipartite graphs, which renders traditional similarity measures less effective. Recognizing that similarity is key to structural clustering, we resort to butterflies—the fundamental building blocks of bipartite graphs—to define a more effective similarity measure. Building on this, we further propose a novel structural clustering model, SBC, tailored for bipartite graphs. To enable clustering under this model, we develop efficient online and index-based methods, along with a dynamic maintenance method to accommodate graph updates over time. Extensive experiments on real-world bipartite graphs demonstrate that: (1) The SBC model greatly enhances clustering quality, achieving higher modularity while effectively identifying outliers and hubs. (2) Our proposed clustering methods are highly scalable, enabling the processing of graphs with up to 12.2 million edges within 2 seconds

Counting the number of shortest paths between two query vertices on road networks has a wide range of applications and has recently drawn significant research attention. The state-of-the-art solution builds a tree-based index using the concept of tree decomposition. However, its performance deteriorates when the tree decomposition results in an unbalanced tree and may not perform well when the query vertices are close to each other. This paper aims to improve the efficiency of shortest path counting. We propose a novel indexing scheme that combines hub labeling with a balanced tree hierarchy. This approach significantly reduces the number of visited labels compared to the state-of-the-art solution. Furthermore, we introduce several optimizations to enhance the efficiency of index construction and minimize its size. Extensive experiments conducted on real-world road networks demonstrate that our method achieves up to 4.1 times higher query efficiency and reduces the index size by a factor of 2.35 compared to the state-of-the-art solution.

Graphs are powerful tools for modeling entities and their relationships. Among the fundamental operations on graphs, path queries play a vital role in identifying paths between pairs of vertices. These queries underpin a broad range of applications by enabling efficient navigation and insightful analysis of graph-structured data. Path queries can be categorized based on the types of paths they return, with each category addressing specific application needs. In this tutorial, we focus on four major categories of path queries: plain shortest path queries, constrained shortest path queries, shortest path summary queries, and non-shortest path queries. We begin by introducing the basic concepts and practical applications of path queries. We then provide an in-depth exploration of the four categories listed above. Finally, we conclude with a discussion of the future research directions in this area.

Approximate K Nearest Neighbor (AKNN) search in high-dimensional spaces is a critical yet challenging problem. In AKNN search, distance computation is the core task that dominates the runtime. Existing approaches typically use approx-imate distances to improve computational efficiency, often at the cost of reduced search accuracy. To address this issue, the state-of-the-art method, ADSampling, employs random projections to estimate approximate distances and introduces an additional distance correction process to mitigate accuracy loss. However, ADSampling has limitations in both effectiveness and generality, primarily due to its heavy reliance on random projections for distance approximation and correction. Motivated by this, we leverage data distribution to improve distance approximation via orthogonal projection, thereby ad-dressing the effectiveness limitation of ADSampling; we also adopt a data-driven approach to distance correction, decoupling the correction process from the distance approximation process, thereby overcoming the generality limitation of ADSampling. Ex-tensive experiments demonstrate the superiority and effectiveness of our method. In particular, compared to ADSampling, our method achieves a speedup of 1.6 to 2.1 times on real-world datasets while providing higher accuracy. In addition, our method shows superior performance in Ant Group image search scenarios and has been integrated into their search engine.

Large-scale graph data has demonstrated significant success in graph representation learning, but the associated high computational cost and inefficiency hinder its widespread adoption across diverse applications. Graph condensation has emerged as a promising solution to reduce time and memory demands while preserving generalization performance comparable to the original graph. Although existing graph condensation methods have proven effective, they are constrained by their reliance on repeatedly optimizing a condensed graph at a fixed scale, which demands significant computational resources and lacks flexibility to accommodate varying training requirements. This motivates us to explore alternative approaches that incrementally refine and expand condensed graphs.

Signed graphs capture both positive and negative relationships between entities, with balance being a fundamental concept. In these graphs, a vertex is considered balanced if all cycles it belongs to contain an even number of negative edges. On the other hand, unbalanced vertices often experience cognitive dissonance and emotional disturbance, motivating efforts to modify the graph to achieve balance for these vertices. Yet, most existing research emphasizes global balance, focusing on lengthy cycles that represent distant interactions. In contrast, this paper shifts the focus to local balance, where a vertex is deemed balanced when the triangles (length-three cycles) it participates in are positive, reflecting more immediate relationships. Building on this, we introduce the Locally Balancing Signed Graph (LBS) problem, which aims to maximize the number of locally balanced vertices through graph modification. Despite the NP-hard nature of the LBS problem and the absence of properties such as monotonicity and submodularity, our novel greedy method effectively addresses these challenges. We further enhance our method with dynamic computation and pruning techniques. Extensive experiments show the efficacy of our greedy method in solving the LBS problem and underscore the substantial runtime reductions achieved through our optimization techniques.

Path enumeration is a fundamental problem and has been extensively studied in the literature. Given two query vertices and a weight threshold, the problem aims to identify all simple paths with weight not exceeding the threshold. Existing studies on path enumeration include DFS-based solutions and join-based solutions, where the join-based solutions only work for unweighted graphs. In this paper, we are the first to propose a join-based framework for weighted graphs. By observing the characteristics of DFS, we design a series of novel data structures and operations based on the join-based framework. In this way, our final solution combines the advantages of both join and DFS. We conduct experiments on several real large graphs. For weighted graphs, our method is much more efficient than existing algorithms. For unweighted graphs, our method is still competitive compared with the state-of-the-art solution which only works for unweighted graphs.

The rapid proliferation of fake news on social media threatens social stability, creating an urgent demand for more effective detection methods. While many promising approaches have emerged, most rely on content analysis with limited semantic depth, leading to suboptimal comprehension of news content. To address this limitation, capturing broader-range semantics is essential yet challenging, as it introduces two primary types of noise: fully connecting sentences in news graphs often adds unnecessary structural noise, while highly similar but authenticity-irrelevant sentences introduce feature noise, complicating the detection process. To tackle these issues, we propose BREAK, a broad-range semantics model for fake news detection that leverages a fully connected graph to capture comprehensive semantics while employing dual denoising modules to minimize both structural and feature noise. The semantic structure denoising module balances the graph's connectivity by iteratively refining it between two bounds: a sequence-based structure as a lower bound and a fully connected graph as the upper bound. This refinement uncovers label-relevant semantic interrelations structures. Meanwhile, the semantic feature denoising module reduces noise from similar semantics by diversifying representations, aligning distinct outputs from the denoised graph and sequence encoders using KL-divergence to achieve feature diversification in high-dimensional space. The two modules are jointly optimized in a bi-level framework, enhancing the integration of denoised semantics into a comprehensive representation for detection. Extensive experiments across four datasets prove that BREAK significantly outperforms existing fake news detection methods.

Hypergraphs provide a versatile framework for modeling complex relationships beyond pairwise interactions, finding applications in various domains. k -core decomposition is a fundamental task in hypergraph analysis that decomposes hypergraphs into cohesive substructures. Existing studies capture the cohesion in hypergraphs based on the vertex neighborhood size. However, such decomposition poses unique challenges, including the efficiency of core value updates, redundant computation, and high memory consumption. We observe that the state-of-the-art algorithms do not fully address the above challenges and are unable to scale to large hypergraphs. In this paper, we propose an efficient approach for hypergraph k -core decomposition. Novel concepts and strategies are developed to compute the core value of each vertex and reduce redundant computation of vertices. Experimental results on real-world and synthetic hypergraphs demonstrate that our approach significantly outperforms the state-of-the-art algorithm by 7 times on average while reducing the average memory usage by 36 times. Moreover, while existing algorithms fail on tens of millions hyperedges, our approach efficiently handles billion-scale hypergraphs in only a single thread.

In real-world road networks, edges possess additional numeric attributes, such as width and toll, in addition to length. Incorporating these additional attributes enhances the functionality of shortest-distance services. To this end, current research on shortest-distance computation requires that the numeric attributes of edges on a path exceed a lower bound$l$(within the interval [l,oo]). However, it often overlooks the benefits of setting an upper bound$r$(within the interval [l, r]). To bridge this gap, we introduce the numeric-constrained shortest-distance query problem, which enforces interval constraints [l, r] on the numeric attributes of edges on a path. There are two intuitive solutions: the Online-Search method, which excludes edges that violate the constraints during the search, leading to inefficient query responses, and the Full-Index method, which creates an index for each necessary interval constraint [l, r], resulting in excessive space consumption due to numerous potential intervals. Our novel index-based method, which uses the tree decomposition technique and exploits interval-distance relationships, aims to mitigate these issues. As confirmed by our experimental results, our method greatly improves query speed - over 20 times faster than Online-Search- and consumes less space than Full-Index.

The acquisition of explicit user feedback (e.g., ratings) in real-world recommender systems is often hindered by the need for active user involvement. To mitigate this issue, implicit feedback (e.g., clicks) generated during user browsing is exploited as a viable substitute. However, implicit feedback possesses a high degree of noise, which significantly undermines recommendation quality. While many methods have been proposed to address this issue by assigning varying weights to implicit feedback, two shortcomings persist: (1) the weight calculation in these methods is iteration-independent, without considering the influence of weights in previous iterations, and (2) the weight calculation often relies on prior knowledge, which may not always be readily available or universally applicable.

In a graph, the reverse nearest neighbors (RNN) of vertex f refer to the set of vertices that consider f as their nearest neighbor. When f represents a facility like a subway station, its RNN comprises potential users who prefer the nearest facility. In practice, there may be underutilized facilities with small RNN sizes, and relocating these facilities to expand their service can be costly or infeasible. A more cost-effective approach involves selectively upgrading some edges (e.g., reducing their weights) to expand the RNN sizes of underutilized facilities. This motivates our research on the Expanding Reverse Nearest Neighbors (ERNN) problem, which aims to maximize the RNN size of a target facility by upgrading a limited number of edges. Solving the ERNN problem allows underutilized facilities to serve more users and alleviate the burden on other facilities. Despite numerous potential applications, ERNN is hard to solve: It can be proven to be NP-hard and APX-hard, and it exhibits non-monotonic and non-submodular properties. To overcome these challenges, we propose novel greedy algorithms that improve efficiency by minimizing the number of edges that need to be processed and the cost of processing each edge. Experimental results demonstrate that the proposed algorithms achieve orders of magnitude speedup compared to the standard greedy algorithm while greatly expanding the RNN.

Structural graph clustering (SCAN) is a popular clustering technique. Using the concept of$\epsilon$-neighborhood, SCAN defines the core vertices that uniquely determine the clusters of a graph. Most existing studies assume that the graph processed by SCAN contains no controlled edges. Few studies, however, have focused on manipulating SCAN by injecting edges. Manipulation of SCAN can be used to assess its robustness and lay the groundwork for developing robust clustering algorithms. To fill this gap and considering the importance of the$\epsilon$-neighborhood for SCAN, we propose a problem, denoted as MN, for manipulating SCAN. The MN problem aims to maximize the$\epsilon$-neighborhood of the target vertex by inserting some edges. On the theoretical side, we prove that the MN problem is both NP-hard and APX-hard, and also is non-submodular and non-monotonic. On the algorithmic side, we design an algorithm by focusing on how to select vertices to join$\epsilon -$neighborhood and thus avoid enumerating edges to report a solution. As a result, our algorithm bypasses the non-monotonicity nature of the MN problem. Extensive experiments on real-world graphs show that our algorithm can effectively solve the proposed MN problem.

Real-world graphs are typically distributed across multiple data centers. When performing reachability queries on these distributed graphs, reachability labeling methods ensure fast query processing by using lightweight indexes. One of the best-known labeling methods is TOL; however, TOL is a serial algorithm and cannot handle distributed graphs. The main goal of this paper is to design new labeling methods that can work in parallel while producing the same index as TOL. To this end, we investigate the limitation of TOL and thus propose a filtering-and-refinement framework for index creation. This framework first obtains a super-set of each vertex's label sets and then eliminates the invalid elements. Based on this framework, we design distributed labeling algorithms and then use batch processing to improve efficiency. Experimental results on real-world graphs show that the proposed algorithms can index distributed graphs efficiently.

Given a graph, eccentricity measures the distance from each node to its farthest node. Eccentricity indicates the centrality of each node and collectively encodes fundamental graph properties: the radius and the diameter --- the minimum and maximum eccentricity, respectively, over all the nodes in the graph. Computing the eccentricities for all the graph nodes, however, is challenging in theory: any approach shall either complete in quadratic time or introduce a 1/3 relative error under certain hypotheses. In practice, the state-of-the-art approach PLLECC in computing exact eccentricities relies heavily on a precomputed all-pair-shortest-distance index whose expensive construction refrains PLLECC from scaling up. This paper provides insights to enable scalable exact eccentricity computation that does not rely on any index. The proposed algorithm IFECC handles billion-scale graphs that no existing approach can process and achieves up to two orders of magnitude speedup over PLLECC. As a by-product, IFECC can be terminated at any time during execution to produce approximate eccentricities, which is empirically more stable and reliable than KBFS, the state-of-the-art algorithm for approximately computing eccentricities.

The shortest path distance and related concepts lay the foundations of many real-world applications in road network analysis. The shortest path count has drawn much research attention in academia, not only as a closeness metric accompanying the shorted distance but also serving as a building block of centrality computation. This paper aims to improve the efficiency of counting the shortest paths between two query vertices on a large road network. We propose a novel index solution by organizing all vertices in a tree structure and propose several optimizations to speed up the index construction. We conduct extensive experiments on 14 real-world networks. Compared with the state-of-the-art solution, we achieve much higher efficiency on both query processing and index construction with a more compact index.

The shortest-path query, which returns the shortest path between two vertices, is a basic operation on complex networks and has numerous applications. To handle shortest-path queries, one option is to use traversal-based methods (e.g., breadth-first search); another option is to use extension-based methods, i.e., extending existing methods that use indexes to handle shortest-distance queries to support shortest-path queries. These two types of methods make different trade-offs in query time and space cost, but comprehensive studies of their performance on real-world graphs are lacking. Moreover, extension-based methods usually use extra attributes to extend the indexes, resulting in high space costs. To address these issues, we thoroughly compare the two types of methods mentioned above. We also propose a new extension-based approach, Monotonic Landmark Labeling (MLL), to reduce the required space cost while still guaranteeing query time. We compare the performance of different methods on ten large real-world graphs with up to 5.5 billion edges. The experimental results reveal the characteristics of various methods, allowing practitioners to select the appropriate method for a specific application.

Centrality measures are widely used to map each node to its importance in a network. For many practical applications, vital nodes bearing high centrality scores have superior positions over other nodes. To benefit from the positive impact of becoming a vital node, the problem of improving the centrality of the target node has attracted increasing attention. Many existing studies attack this problem by directly increasing the centrality score of the target node on the premise of knowing the network structure. However, these methods suffer from privacy issues due to their dependence on the network structure and may lose their effectiveness because other nodes can simultaneously increase the scores. Therefore, in this paper, we explore the following question: given a black-box network whose structure is unknown, is it possible to improve the centrality ranking (rather than the score) of a target node by implementing certain strategies? We provide an affirmative answer to this question. First, to avoid relying on the network structure for promotion, we propose strategies that freeze the original graph while appending nodes and edges just around the target node. Second, to guide strategies for effectively boosting centrality, we devise two principles that provide the target node with either the maximum gain or the minimum loss of centrality scores over other nodes. We prove that a strategy meeting the proposed principles is guaranteed to upgrade the target node's ranking. Extensive experiments were conducted to verify the effectiveness of the proposed strategies on black-box networks.

Computing the shortest path between two vertices is a fundamental problem in road networks. Most of the existing works assume that the edges in the road networks have no labels, but in many real applications, the edges have labels and label constraints may be placed on the edges appearing on a valid shortest path. Hence, we study the label-constrained shortest path queries in this paper. In order to process such queries efficiently, we adopt an index-based approach and propose a novel index structure, LSD-Index, based on tree decomposition. With LSD-Index, we design an efficient query processing algorithm with good performance guarantees. Moreover, we also propose an algorithm to construct LSD-Index and further improve the efficiency of index construction by exploiting the parallel computing techniques. We conduct extensive performance studies using large real road networks including the whole USA road network. Compared with the state-of-the-art approach, the experimental results demonstrate that our algorithm not only achieves up to 2 orders of magnitude speedup in query processing time but also consumes much less index space. Meanwhile, the indexing time is also competitive, especially that for the parallel index construction algorithm.

In indexing a graph for distance queries, distance labeling is a common practice; in particular, 2-hop labeling which guarantees the exactness of the query results is widely adopted. When it comes to a massive real graph with a relatively large treewidth such as social networks and web graphs, however, 2-hop labeling can hardly be constructed due to the oversized index. This paper discloses the theoretical relationships between the graph treewidth and 2-hop labeling's index size and query time. To scale up distance labeling, this paper proposes Core-Tree (CT) Index to facilitate a critical and effective trade-off between the index size and query time. The reduced index size enables CT-Index to handle massive graphs that no existing approaches can process while the cost in the query time is negligible: the query time is below 0.4 milliseconds on all tested graphs including one graph with 5.5 billion edges.

Distance labeling approaches are widely adopted to speed up the online performance of shortest distance queries. The construction of the distance labeling, however, can be exhaustive especially on big graphs. For a major category of large graphs, small-world networks, the state-of-the-art approach is Pruned Landmark Labeling (PLL). PLL prunes distance labels based on a node order and directly constructs the pruned labels by performing breadth-first searches in the node order. The pruning technique, as well as the index construction, has a strong sequential nature which hinders PLL from being parallelized. It becomes an urgent issue on massive small-world networks whose index can hardly be constructed by a single thread within a reasonable time. This paper scales distance labeling on small-world networks by proposing a Parallel Shortest-distance Labeling (PSL) scheme and further reducing the index size by exploiting graph and label properties. PSL insightfully converts the PLL's node-order dependency to a shortest-distance dependence, which leads to a propagation-based parallel labeling in D rounds where D denotes the diameter of the graph. Extensive experimental results verify our efficiency on billion-scale graphs and near-linear speedup in a multi-core environment.

This paper studies the efficiency issue on computing the exact eccentricity-distribution of a small-world network. Eccentricity-distribution reflects the importance of each node in a graph, which is beneficial for graph analysis. Moreover, it is key to computing two fundamental graph characters: diameter and radius. Existing eccentricity computation algorithms, however, are either inefficient in handling large-scale networks emerging nowadays in practice or approximate algorithms that are inappropriate to small-world networks. We propose an efficient approach for exact eccentricity computation. Our approach is based on a plethora of insights on the bottleneck of the existing algorithms — one-node eccentricity computation and the upper/lower bounds update. Extensive experiments demonstrate that our approach outperforms the state-of-the-art up to three orders of magnitude on real large small-world networks.