Mining temporal motifs in temporal graphs is essential for many critical applications. Although several solutions have been proposed to handle temporal motif mining, they still suffer from substantial inefficiencies due to significant redundant graph traversals and fragmented memory access, both caused by irregular search tree expansions across different motif matching tasks. In this work, we observe that data accesses issued by these tasks exhibit strong spatial similarity and temporal monotonicity. Based on these observations, this paper proposes an efficient data-centric temporal motif mining system DTMiner, which introduces a novel Load-Explore-Synchronize (LES) execution model to efficiently regularize data accesses to the common temporal graph data among different tasks. Specifically, DTMiner enables the temporal graph chunks to be sequentially loaded into the cache in temporal order and then triggers all relevant tasks to explore only these loaded data for search tree expansions in a fine-grained synchronization mechanism. In this way, different tasks can share the graph traversal corresponding to the same chunks, while fragmented memory accesses are restricted to the graph data residing in the cache, significantly reducing data access overhead. Experimental results demonstrate that DTMiner achieves 1.14×-11.98× performance improvement in comparison with the state-of-the-art temporal motif mining solutions.

Bipartite graphs are widely used to model relationships between entities of different types, where vertices are divided into two disjoint sets. Biclique-preserving clustering is a fundamental operation that retrieves clusters with dense bicliques, enabling various emerging applications. However, existing methods either fail to accurately capture the unique properties of bipartite graphs or significantly overlook the informative higher-order biclique substructure, leading to compromised clustering quality. Additionally, existing methods are overly dependent on biclique enumeration, resulting in poor scalability. To address these challenges, we propose ECRC, a simple yet provable Edge-Centric Reweighting Clustering framework that provides strict approximation guarantees for any biclique. A key advantage of ECRC is its ability to leverage powerful counting instead of exhaustive enumeration, significantly reducing time and space complexity. To further improve efficiency, we propose several effective graph reduction strategies to eliminate the unqualified vertices and edges before calculating the edge-centric weight. Extensive experiments on five datasets show that our algorithms are more efficient and effective compared to six baselines.

Contrastive learning has demonstrated strong performance in attributed hypergraph clustering. Typically, existing methods based on contrastive learning first learn node embeddings and then apply clustering algorithms, such as k-means, to these embeddings to obtain the clustering results.However, these methods lack direct clustering supervision, risking the inclusion of clustering-irrelevant information in the learned graph. To this end, we propose a Contrastive learning approach for Attributed Hypergraph Clustering (CAHC), an end-to-end method that simultaneously learns node embeddings and obtains clustering results. CAHC consists of two main steps: representation learning and cluster assignment learning. The former employs a novel contrastive learning approach that incorporates both node-level and hyperedge-level objectives to generate node embeddings.The latter joint embedding and clustering optimization to refine these embeddings by clustering-oriented guidance and obtains clustering results simultaneously.Extensive experimental results demonstrate that CAHC outperforms baselines on eight datasets.

Neural network models in natural language processing have demonstrated remarkable proficiency, but they are still vulnerable to adversarial attacks, where minute and indistinguishable alterations can profoundly disturb their performance. Existing methods struggle to define synonyms accurately and rely on greedy traversal or gradient computation, making them difficult to deploy. Inspired by these, this paper proposes a novel text adversarial attack method, which constructs rich candidate adversarial examples by non-trivially combining theGranular-Ball computing andDifferentialEvolution, termed GBDE. Through iterative optimization guided by a meticulously crafted loss function, GBDE iteratively optimizes to generate effective and high-quality adversarial examples. Specifically, GBDE realizes a multi-granularity granular-ball clustering method following the data features, to establish robust synonym sets. It then performs synonym substitutions on target samples to create candidate adversarial samples and further diversifies these samples through a customized differential evolution process. Additionally, the loss function incorporates a reward and punishment mechanism to steer the optimization of attacks. Empirical results showcase GBDE's superiority when contrasted with cutting-edge models. Notably, GBDE produces high-quality adversarial texts with a larger success rate. Besides, ablation studies confirm the contributions of granular-ball clustering and differential evolution in text attacks, and the rationality of the loss function design.

Temporal graph neural networks (T-GNNs) have emerged as an effective paradigm for learning dynamic node representations by modeling the temporal evolution of graph structures. Among them, personalized PageRank (PPR)-based T-GNNs have recently gained increasing attention due to their strong empirical performance and theoretical grounding. Nevertheless, existing PPR-based T-GNN methods suffer from two fundamental limitations. First, their aggregation mechanisms are typically restricted to lower order neighborhoods, which hinders the capture of higher order temporal dependences and leads to degraded performance. Second, feature propagation and feature transformation are often tightly coupled, resulting in limited scalability on large temporal graphs. To overcome these challenges, we propose temporal personalized PageRank with spectral sparsification (TPPSS), a novel framework that seamlessly incorporates temporal information into the PPR formulation while decoupling propagation from transformation through a polynomial spectral sparsification. A key technical contribution ofTPPSSlies in a unified matrix-based formulation that replaces the conventional rowwise computation of PPR-like scores, enabling efficient and scalable. Moreover, by leveraging spectral sparsification,TPPSSconstructs a sparse computational graph that effectively suppresses noise and redundancy. Extensive experiments on six datasets showcase the effectiveness, efficiency, and scalability of our solutions compared to eight competitors.

Important communities are densely connected subgraphs containing vertices with high importance values, which have received wide attention recently. However, existing methods, predominantly based on the$k$-core model, suffer from limitations such as rigid degree constraints and suboptimal density, often failing to capture highly important vertices. To address these limitations, we propose a new community model based on pseudoarboricity that guarantees near-optimal density while preserving important vertices. Further, we introduce a novel problem of Psudoarboricity-based Skyline Important Community (PSIC), which uniquely treats density and importance as independent attributes. To efficiently address PSIC, we first devise a basic algorithm climbStairs, which iteratively refines communities by peeling vertices with low importance. To boost efficiency, we develop an advanced algorithm DivAndCon, which employs a recursive divide-and-conquer strategy combined with weight-based and pseudoarboricity-based pruning techniques, significantly reducing the search space. For massive graphs with billions of edges, inspired by a recursive division tree, we develop several parallel algorithms utilizing thread-pool and free-synchronization mechanism. Finally, we conduct extensive experiments on 10 real-world networks, and the results demonstrate the superiority of our solutions in terms of effectiveness, efficiency, and scalability.

Identifying locally dense communities closely connected to the user-initiated query node is crucial for a wide range of applications. Existing approaches either solely depend on rule based constraints or exclusively utilize deep learning technologies to identify target communities. Therefore, an important question is proposed: can deep learning be integrated with rule-based constraints to elevate the quality of community search? In this paper, we affirmatively address this question by introducing a novel approach called Neural Community Search via Attribute augmented Conductance, abbreviated as NCSAC. Specifically, NCSAC first proposes a novel concept of attribute-augmented conductance, which harmoniously blends the (internal and ex ternal) structural proximity and the attribute similarity. Then, NCSAC extracts a coarse candidate community of satisfactory quality using the proposed attribute-augmented conductance. Subsequently, NCSAC frames the community search as a graph optimization task, refining the candidate community through sophisticated reinforcement learning techniques, thereby producing high-quality results. Extensive experiments on six real world graphs and ten competitors demonstrate the superiority of our solutions in terms of accuracy, efficiency, and scalability. Notably, the proposed solution outperforms state-of-the-art methods, achieving an impressive F1-score improvement ranging from 5.3% to 42.4%. For reproducibility purposes, the source code is available at https://github.com/longlonglin/ncsac.

Bipartite graphs are widely used to model relationships between entities of different types, where nodes are divided into two disjoint sets. Similarity search, a fundamental operation that retrieves nodes similar to a given query node, plays a crucial role in various real-world applications, including machine learning and graph clustering. However, existing state of-the-art methods often struggle to accurately capture the unique structural properties of bipartite graphs or fail to incorporate the informative node attributes, leading to suboptimal performance. Besides, their high computational complexity limits scalability, making them impractical for large graphs with millions of nodes and tens of thousands of attributes. To overcome these challenges, we first introduce Attribute-augmented Hidden Personalized PageRank (AHPP), a novel random walk model designed to blend seamlessly both the higher-order bipartite structure proximity and attribute similarity. We then formulate the similarity search over attributed bipartite graphs as an approximate AHPP problem and propose two efficient push-style local algorithms with provable approximation guarantees. Finally, extensive experiments on real-world and synthetic datasets validate the effectiveness of AHPP and the efficiency of our proposed algorithms when compared with fifteen competitors.

Tackling temporal path problems in temporal graphs is essential for time-sensitive applications. Although many solutions have been proposed to handle temporal path problems, due to the intrinsic time constraints, these solutions require the vertices of the temporal graph to be sequentially handled along the time-dependent chains (i.e., the temporal dependencies between these vertices) to form the temporal path. This sequential temporal nature poses the challenges of poor parallelism and slow convergence speed, preventing existing solutions from fully leveraging the massive parallelism and high internal bandwidth of GPU to handle temporal path problems. To overcome these challenges, this paper proposes TempGraph, an efficient chain-driven GPU-based temporal graph computing framework. Specifically, it transforms the temporal graph into a set of disjoint time-dependent chains that can elegantly expose the temporal dependency between the vertices while facilitating the fast path exploration along these chains over GPU. Furthermore, TempGraph employs a novel Generate-Activate-Compute execution model to decouple the temporal dependency between different chains through maintaining a set of shortcuts for them, which enables multiple chains to be concurrently handled by massive GPU threads, achieving fast convergence speed and high parallelism on the GPU. Experiments on an A100 GPU show that TempGraph outperforms the state-of-the-art GPU-based solutions by 3.0-16.2×. Besides, TempGraph on an A100 GPU gains 33.9-368.9× speedups compared to the cutting-edge CPU-based system TeGraph on a 128-core CPU machine.

Adaptive Radix Tree (ART) is a widely used tree index structure prevalent in various domains such as databases and key-value stores. Despite many solutions have been proposed to improve the performance of ART, they still suffer from significant redundant tree traversals and serious synchronization cost when concurrently performing the operations (e.g., read/write) over ART. In this work, we observe that most operations of realworld workloads tend to target a small subset of ART nodes frequently, exhibiting strong temporal and spatial similarities among the operations. Based on this observation, we propose a data-centric hardware accelerator, called DCART, to efficiently support the operations over ART. Specifically, DCART proposes a novel data-centric processing model into the accelerator design to coalesce the operations associated with the same ART nodes and adaptively cache the frequently traversed ART nodes and their search results, thereby fully exploiting the similarities among the operations for lower tree traversal and synchronization overhead. We implemented DCART on the Xilinx Alveo U280 FPGA card and compared it with the cutting-edge solutions, DCART achieves $21.1 \times-44.2 \times$ speedups and $71.1 \times-148.9 \times$ energy savings.

Temporal-constraint subgraph matching has emerged as a significant challenge in the study of temporal graphs, which model dynamic relationships across various domains, such as social networks and transaction networks. However, the problem of temporal-constraint subgraph matching is NP-hard. Furthermore, because each temporal-constraint contains a permutation of temporal parameters, existing subgraph matching acceleration techniques demonstrate limited applicability to temporal-constrained graphs. Traditional continuous subgraph matching approaches prove inadequate in addressing this complex problem due to their inability to effectively handle temporal constraints. This paper addresses the challenge of identifying subgraphs that not only structurally align with a given query graph but also satisfy specific temporal-constraints on the edges. We introduce three novel algorithms to tackle this issue: the TCSM-V2V algorithm, which uses a vertex-to-vertex expansion strategy and effectively prunes non-matching vertices by integrating both query and temporal-constraints into a temporal-constraint query graph; the TCSM-E2E algorithm, which employs an edge-to-edge expansion strategy, significantly reducing matching time by minimizing vertex permutation processes; and the TCSM-EVE algorithm, which combines edge-vertex-edge expansion to eliminate duplicate matches by avoiding both vertex and edge permutations. Notably, our optimal TCSM-EVE algorithm achieves an average three-order-of-magnitude speedup on large-scale datasets. Extensive experiments conducted across 6 datasets demonstrate that our approach outperforms existing methods in terms of both accuracy and computational efficiency.

Graph Neural Networks (GNNs) have garnered substantial attention due to their remarkable capability in learning graph representations. However, real-world graphs often exhibit substantial noise and incompleteness, which severely degrades the performance of GNNs. Existing methods typically address this issue through single-dimensional augmentation, focusing either on refining topology structures or perturbing node attributes, thereby overlooking the deeper interplays between the two. To bridge this gap, this paper presents CoATA, a dual-channel GNN framework specifically designed for the Co-Augmentation of Topology and Attribute. Specifically, CoATA first propagates structural signals to enrich and denoise node attributes. Then, it projects the enhanced attribute space into a node-attribute bipartite graph for further refinement or reconstruction of the underlying structure. Subsequently, CoATA introduces contrastive learning, leveraging prototype alignment and consistency constraints, to facilitate mutual corrections between the augmented and original graphs. Finally, extensive experiments on seven benchmark datasets demonstrate that the proposed CoATA outperforms eleven state-of-the-art baseline methods, showcasing its effectiveness in capturing the synergistic relationship between topology and attributes.

The densest subgraph (DS) search over a directed graph focuses on finding the subgraph with the highest density among all subgraphs. This problem has raised numerous applications, such as fraud detection and community detection. The state-of-the-art DS algorithms have prohibitively high costs or poor approximation ratios, making them unsuitable for practical applications. To address these dilemmas, in this paper, we propose a novel model called integral densest subgraph (IDS). We show that IDS can serve as a near-DS model that has a tight floor relationship with the density of the DS. To compute IDS, we first propose a novel flow network named (α,β)-dense network, based on which we design an exact network-flow algorithm GetIDS with O(p • log |V| • |E| 1.5 ) time complexity, where p is typically a small constant in real-world graphs. Additionally, we propose several non-trivial pruning techniques to further improve the efficiency. Subsequently, we propose a novel (2 + ε)-approximation algorithm MultiCore with near-linear time complexity, providing a good approximation guarantee with high efficiency. Finally, our extensive experiments on 10 real-world graphs demonstrate the effectiveness of the proposed IDS model, and the high efficiency and scalability of the proposed solutions.

Learned indexes have attracted significant research interest due to their potential to offer better space-time trade-offs compared to B+-tree variants. Among various learned indexes, the PGM-Index based on error-bounded piecewise linear approximation is an elegant data structure that has demonstrated provably superior performance over conventional B+-tree indexes. However, despite numerous efforts to optimize the design of the PGM-Index, few systematically study the root causes of performance mismatches observed in practice. In this paper, we explore two key research questions. Q1 : Why are PGM-Indexes theoretically effective? and Q2 : Why do PGM-Indexes underperform in practice? For Q1 , we show that for a set of N sorted keys, the PGM-Index can achieve a lookup time of O (log log N ) while using O ( N ) space. For Q2 , we identify that querying PGM-Indexes is highly memory-bound, where the internal index search operations often become the bottleneck. To fill the performance gap, we propose PGM++, a simple yet effective extension to the original PGM-Index that employs a mixture of different search strategies, with hyper-parameters automatically tuned through a cost model calibrated by theoretical findings. Extensive experiments show that, at comparable space costs, PGM++ speeds up index lookup queries by up to 2.31X and 1.56X when compared to the original PGM-Index and SOTA baselines.

Truss decomposition is a fundamental approach in graph theory that focuses on uncovering cohesive subgraphs within networks. However, many networks involve groupwise rather than pairwise relationships and are often represented as hypergraphs. Modeling and capturing k-truss in hypergraphs is essential for uncovering tight-knit relationships in such multi-relational networks. In this paper, we tackle the problem of truss decomposition in hypergraph. A hyper k-truss is a subgraph in which each node is part of at least k hyper-triangles. We first introduce a framework for hyper-truss decomposition and determine that the most time-consuming component is counting hyper-triangles. To count all hyper-triangles efficiently, we propose an edge-iterator algorithm. To further reduce redundant computations, we present an improved algorithm that combines edge-iterator and node-iterator techniques to prune non-promising nodes. Next, to handle common nodes in hypergraphs, we develop a novel prefix forest technique to encode all hyperedges and count triangles within this prefix forest. We also propose several optimization strategies that reorder nodes and hyperedges to improve work balancing. Finally, we conduct extensive experiments on real-world hypergraph datasets, demonstrating the efficiency and effectiveness of our algorithms.

Community search is a widely studied semi-supervised graph clustering problem, retrieving a high-quality connected subgraph containing the user-specified query vertex. However, existing methods primarily focus on cohesiveness within the community but ignore the sparsity outside the community, obtaining sub-par results. Inspired by this, we adopt the well-knownconductancemetric to measure the quality of a community and introduce a novel problem ofconductance-based community search (CCS).CCSaims at finding a subgraph with the smallestconductanceamong all connected subgraphs that contain the query vertex. We prove that theCCSproblem is NP-hard. To efficiently queryCCS, a four-stagesubgraph-conductance-based community search algorithm,SCCS, is proposed. Specifically, we first greatly reduce the entire graph using local sampling techniques. Then, a three-stage local optimization strategy is employed to continuously refine the community quality. Namely, we first utilize a seeding strategy to obtain an initial community to enhance its internal cohesiveness. Then, we iteratively add qualified vertices in the expansion stage to guarantee the internal cohesiveness and external sparsity of the community. Finally, we gradually remove unqualified vertices during the verification stage. Extensive experiments on real-world datasets containing one billion-scale graph and synthetic datasets show the effectiveness, efficiency, and scalability of our solutions.

Higher-order graph clustering partitions graphs use frequently occurring subgraphs instead of edges, proving effective in community detection and knowledge discovery. Motif conductance, known for its strong interpretability, is a leading model. However, existing motif conductance algorithms are hindered by a two-stage reweighting framework that requires enumerating motif instances to generate an edge-weighted graph for partitioning. This framework has two major drawbacks: (1) It provides only a quadratic bound for three-vertex motifs, with no provable approximation guarantees for other motifs. (2) Enumerating motif instances is computationally prohibitive for large motifs or dense graphs due to combinatorial explosions. Besides, costly spectral clustering or local graph diffusion on the edge-weighted graph limits their scalability. In this paper, we propose a novel peeling-based clustering framework, PSMC, offering a motifindependent approximation ratio for any motif. Specifically, PSMC first defines a new locally computable vertex metric Motif Resident based on the given motif. Then, it iteratively deletes vertices with the smallest motif resident using efficient dynamic update techniques, outputting a locally optimal result with approximation guarantees. Besides, we introduce several powerful optimization techniques to further reduce computational costs. Empirical results on real-world and synthetic datasets showcase our proposed solutions' superiority over ten competitors.

Network embedding has numerous practical applications and has received extensive attention in graph learning, which aims at mapping vertices into a low-dimensional and continuous dense vector space by preserving the underlying structural properties of the graph. Many network embedding methods have been proposed, among which factorization of the Personalized PageRank (PPR for short) matrix has been empirically and theoretically well supported recently. However, several fundamental issues cannot be addressed. (1) Existing methods invoke a seminal Local Push subroutine to approximate a single row or column of the PPR matrix. Thus, they have to execute n (n is the number of nodes) Local Push subroutines to obtain a provable PPR matrix, resulting in prohibitively high computational costs for large n. (2) The PPR matrix has limited power in capturing the structural similarity between vertices, leading to performance degradation. To overcome these dilemmas, we propose PSNE, an efficient spectral sParsification method for Scaling Network Embedding, which can fast obtain the embedding vectors that retain strong structural similarities. Specifically, PSNE first designs a matrix polynomial sparser to accelerate the calculation of the PPR matrix, which has a theoretical guarantee in terms of the Frobenius norm. Subsequently, PSNE proposes a simple but effective multiple-perspective strategy to enhance further the representation power of the obtained approximate PPR matrix. Finally, PSNE applies a randomized singular value decomposition algorithm on the sparse and multiple-perspective PPR matrix to get the target embedding vectors. Experimental evaluation of real-world and synthetic datasets shows that our solutions are indeed more efficient, effective, and scalable compared with ten competitors.

Higher-order graph clustering aims to partition the graph using frequently occurring subgraphs (i.e., motifs), instead of the lower-order edges, as the atomic clustering unit, which has been recognized as the state-of-the-art solution in ground truth community detection and knowledge discovery. Motif conductance is one of the most promising higher-order graph clustering models due to its strong interpretability. However, existing motif conductance based graph clustering algorithms are mainly limited by a seminal two-stage reweighting computing framework, needing to enumerate all motif instances to obtain an edge-weighted graph for partitioning. However, such a framework has two-fold vital defects: (1) It can only provide a quadratic bound for the motif with three vertices, and whether there is provable clustering quality for other motifs is still an open question. (2) The enumeration procedure of motif instances incurs prohibitively high costs against large motifs or large dense graphs due to combinatorial explosions. Besides, expensive spectral clustering or local graph diffusion on the edge-weighted graph also makes existing methods unable to handle massive graphs with millions of nodes. To overcome these dilemmas, we propose a Provable and Scalable Motif Conductance algorithm PSMC, which has a fixed and motif-independent approximation ratio for any motif. Specifically, PSMC first defines a new vertex metric Motif Resident based on the given motif, which can be computed locally. Then, it iteratively deletes the vertex with the smallest motif resident value very efficiently using novel dynamic update technologies. Finally, it outputs the locally optimal result during the above iterative process. To further boost efficiency, we propose several effective bounds to estimate the motif resident value of each vertex, which can greatly reduce computational costs. Empirical results on real-life and synthetic demonstrate that our proposed algorithms achieve 3.2-32 times speedup and improve the quality by at least 12 times than the state-of-the art baselines.

The quest to identify local dense communities closely connected to predetermined seed nodes is vital across numerous applications. Given the seed nodes R, the R-subgraph density of a subgraph S is defined as traditional graph density of S with penalties on the nodes in S / R. The state-of-the-art (SOTA) anchored densest subgraph model, which is based on R-subgraph density, is designed to address the community search problem. However, it often struggles to efficiently uncover truly dense communities. To eliminate this issue, we propose a novel NR-subgraph density metric, a nuanced measure that identifies communities intimately linked to seed nodes and also exhibiting overall high graph density. We redefine the anchored densest subgraph search problem through the lens of NR-subgraph density and cast it as a Linear Programming (LP) problem. This allows us to transition into a dual problem, tapping into the efficiency and effectiveness of convex programming-based iterative algorithm. To solve this redefined problem, we propose two algorithms: FDP, an iterative method that swiftly attains near-optimal solutions, and FDPE, an exact approach that ensures full convergence. We perform extensive experiments on 12 real-world networks. The results show that our proposed algorithms not only outperform the SOTA methods by 3.6~14.1 times in terms of running time, but also produce subgraphs with superior internal quality.

Deep learning has achieved outstanding performance in natural language processing, but actuality has witnessed its fragility against adversarial attacks. Synonyms-based attacks are most disastrous since their generated samples approximate raw inputs. Several countermeasures have been proposed in the literature, but the defense effectiveness is unsatisfactory because of the clumsy single-granularity synonyms clustering. To mitigate this dilemma, we propose a Granular-Ball Sample Enhancement-based defense Framework (GBSEF) for text adversarial attacks. Specifically, GBSEF first adopts an effective general synonyms clustering algorithm, which can adaptively adjust the granularity of synonym sets (i.e., granular-balls) for diverse datasets. Regarding each ball as a dot, the function consisting of most dots well fits the original data distribution, resulting in the relationships among words being well presented by the granular-balls. GBSEF then replaces each input word with the center vector of its subordinate ball, to construct robust samples preserving syntax and semantic information simultaneously. Finally, GBSEF combines a random substitution mechanism with granular-balls. This way can prompt GBSEF to take full advantage of the multi-granularity feature of granular-balls, to get more diverse valid samples. GBSEF obtains great performance through training on these samples. Abundant evaluations demonstrate the robustness and effectiveness of GBSEF against adversarial attacks, albeit with a slight performance decrease under normal scenarios without attacks. Meanwhile, GBSEF has good transferability against adversarial samples. Compared with state-of-art defense countermeasures, under multiple attacks on four neural network models (i.e., CNN, LSTM, Bi-LSTM, BERT), GBSEF always outperforms existing baselines.

Most natural language processing tasks rely on massive labeled data to train an outstanding neural network model. However, the label noise (i.e., wrong label) is inevitably introduced when annotating large-scale text datasets, which significantly degrades the performance of neural network models. To overcome this dilemma, we propose a novel Granular-B all based tRAINing framework, named GBRAIN, to realize robust coarse-grained representation learning, thus combating label noises in diverse text tasks. Specifically, considering that most samples in the dataset are precisely labeled, GBRAIN first proposes a dynamic granular-ball clustering algorithm to blend seamlessly into the traditional neural network model. A striking feature of the clustering algorithm is that it can adaptively group the embedding vectors of similar data into the same set (hereafter referred to as a granular-ball). The embedding vectors and labels of all samples from the same set will be coarse-grainedly represented by the center vector and the label of the granular-ball, respectively. Consequently, noise labels can be rectified through the labels of most of the labeled data. Moreover, we introduce a new gradient backpropagation mechanism compatible with our framework, which can help optimize coarse-grained embedding vectors with iterative training. Empirical results on text classification and name entity recognition tasks demonstrate that our proposal GBRAIN is indeed effective in contrast to the state-of-the-art baselines.

Graph Neural Networks (GNNs) have achieved remarkable performance in various applications, including social media analysis, computer vision, and natural language processing. Decoupled GNNs are a ubiquitous framework because of their high efficiency. However, existing decoupled GNNs suffer from the following several defects. (1) Their studies on GNN feature propagation are isolated, with each study emphasizing a user-specified propagation matrix. (2) They still have high computation costs to achieve provable performance on massive graphs with millions of nodes and billions of edges. (3) Their feature propagation steps are uniform, which makes it difficult for them to escape the dilemmas of over-smoothing. In this paper, we propose GSD-GNN, a Generalized and Scalable Decoupled GNN framework based on the spectral graph theory, which offers the following advantages. Firstly, through minor parameter adjustments, it can degenerate into most existing Decoupled GNNs, such as APPNP, GDC, SGC, etc. Secondly, it efficiently computes an arbitrary propagation matrix with near-linear time complexity and theoretical guarantees. Thirdly, it customizes the adaptive feature propagation mechanism for each node to mitigate the over-smoothing dilemma. Finally, extensive experiments on massive graphs demonstrate that the proposed GSD-GNN indeed is effective, scalable, and flexible.

Temporal community search is an important task in graph analysis, which has been widely used in many practical applications. However, existing methods suffer from two major defects: (i) they only require that the target result contains the query vertexq, leading to the temporal proximity betweenqand other vertices being ignored. Thus, they may find many temporal irrelevant vertices (these vertices are called query-drifted vertices) concerningqfor satisfying their objective functions; (ii) their methods are NP-hard, incurring high costs for exact solutions or compromised qualities for approximate/heuristic algorithms. In this paper, we propose a new problem named query-centered temporal community search to overcome these limitations. Specifically, we first present a novel concept of Time-Constrained Personalized PageRank to characterize the temporal proximity betweenqand other vertices. Then, we introduce a model calledβ-temporal proximity core, which can seamlessly combine temporal proximity and structural cohesiveness. Subsequently, our problem is formulated as an optimization task that finds aβ-temporal proximity core with the largestβ.We theoretically prove that our problem can circumvent these query-drifted vertices. To solve our problem, we first devise an exact and near-linear time greedy removing algorithm that iteratively removes unpromising vertices. To improve efficiency, we then design an approximate two-stage local search algorithm with bound-based pruning techniques. Finally, extensive experiments on eight real-life datasets and nine competitors show the superiority of the proposed solutions.

Graph coarsening techniques aim at simplifying the graph structure while preserving key properties in the resulting coarsened graph, have been widely used in graph partitioning and graph neural networks (GNNs). Existing graph coarsening techniques mainly focus on preserving cuts or graph spectrums. In this paper, we propose a new method that focuses on preserving graph topological features. In particular, we develop a novel graph coarsening approach, called Graph Elementary Collapse (GEC), by extending the concept of elementary collapse in algebraic topology to graph analysis. With this novel method, we can ensure a kind of equivalence relationship called homotopy equivalence of the graph during the coarsening process, thereby preserving numerous topological properties, including connectivity, rings, and voids. To enhance the scalability, we also propose several carefully-designed optimization techniques to reduce the time and memory consumption of our approach. Extensive experiments on several real-world datasets demonstrate the effectiveness and efficiency of our proposed method across various GNN prediction tasks.

Conductance-based graph clustering has been recognized as a fundamental operator in numerous graph analysis applications. Despite the significant success of conductance-based graph clustering, existing algorithms are either hard to obtain satisfactory clustering qualities, or have high time and space complexity to achieve provable clustering qualities. To overcome these limitations, we devise a powerful peeling-based graph clustering framework PCon. We show that many existing solutions can be reduced to our framework. Namely, they first define a score function for each vertex, then iteratively remove the vertex with the smallest score. Finally, they output the result with the smallest conductance during the peeling process. Based on our framework, we propose two novel algorithms PCon_core and PCon_de with linear time and space complexity, which can efficiently and effectively identify clusters from massive graphs with more than a few billion edges. Surprisingly, we prove that PCon_de can identify clusters with near-constant approximation ratio, resulting in an important theoretical improvement over the well-known quadratic Cheeger bound. Empirical results on real-life and synthetic datasets show that our algorithms can achieve 5~42 times speedup with a high clustering accuracy, while using 1.4~7.8 times less memory than the baseline algorithms.

Temporal subgraph mining is recently ubiquitous. Identifying diversified and lasting ingredients is a fundamental problem in analyzing temporal networks. In this paper, we investigate the problem of finding diversified lasting cohesive subgraphs from temporal networks. Specifically, we first introduce a new model, called maximal lasting$(k,\sigma)$-core, for characterizing lasting cohesive subgraphs on temporal networks so as to the nodes in the subgraph are connected densely and also the subgraph's structure remains unchanged for a period of time. To enhance the diversity of results, we then formulate a diversified lasting cohesive subgraphs problem, which finds$r$maximal lasting$(k,\sigma)$-cores with maximum coverage regarding the number of vertices and timestamps. Unfortunately, we show that the optimization problem is NP-hard. To tackle this issue, we first devise a greedy algorithm namedGreLCwith (1-1/e) approximation ratio. However,GreLChas prohibitively high time and space complexity, resulting in poor scalability. Then, an improved DFS-based search algorithm calledTopLCwith 1/4 approximation ratio is proposed to lower the computational cost. Finally, empirical studies on six real-world temporal networks demonstrate that the proposed solutions perform efficiently and accurately, and our model is better than temporal cohesive subgraphs detected by existing approaches.

Real-world networks, such as phone-call networks and social networks, are often not static but temporal. Mining cohesive subgraphs from static graphs is a fundamental task in network analysis and has been widely investigated in the past decades. However, the concepts of cohesive subgraphs shift from static to temporal graphs raise many important problems. For instance, how to detect stable cohesive subgraphs on temporal networks such that the nodes in the subgraph are densely and stably connected over time. To address this problem, we resort to the conventional quasi-clique and propose a new model, called maximal$\rho $-stable ($\delta, \gamma $)-quasi-clique, to capture both the cohesiveness and the stability of a subgraph. We show that the problem of enumerating all maximal$\rho $-stable ($\delta, \gamma $)-quasi-cliques is NP-hard. To efficiently tackle our problem, we first devise a novel temporal graph reduction algorithm to significantly reduce the temporal graph without losing any maximal$\rho $-stable ($\delta, \gamma $)-quasi-clique. Then, on the reduced temporal graph, we propose an effective branch and bound enumeration algorithm, namedBB&SCM, with four carefully designed pruning techniques to accomplish the enumeration process. Finally, we conduct extensive experiments on seven real-world temporal graphs, and the results demonstrate that the temporal graph reduction algorithm can safely reduce 98% nodes of the temporal graph (with millions of nodes and edges) andBB&SCMis at least two orders of magnitude faster than the baseline algorithms. Moreover, we also evaluate the effectiveness of our model against other baseline models.

RDF data is big and continues to grow rapidly. RDF data sets are typically viewed as heterogeneous graph data sets with complex correlations and multifaceted heterogeneity. Although there have been flurry of research on processing and analyzing RDF data, efficient storage, computation, analysis of big and growing RDF data continue to challenge multiple computer science disciplines, ranging from systems, network computing, data management to data analytics. In this paper, we make use of strawman arguments on big RDF data challenges with respect to storage, computation, analysis, focusing on identifying the grand challenges in developing high performance RDF storage, parallel computation, efficient distribution, and smart RDF analytics. We attempt to answer a number of important and frequently asked questions: (1) Do we really need RDF-specific storage techniques and algorithms for building efficient and high performance RDF stores? (2) How hard can it be to effectively parallelize big RDF data for high performance storage, computation, and mining? (3) What type of distribution models can we employ to scale RDF processing models and algorithms for real-time querying (subgraph pattern matching) and mining of big RDF data? (4) Can machine learning algorithms be leveraged to effectively mine and dive into RDF data? We attempt to answer these questions by sharing some of our results, our unique experiences, and our lessons learned from a collection of research projects in RDF systems research and development. We will also discuss our ongoing research endeavors, potential applications and avenues for future work.

Dynamicity is one of the critical characteristics and a major challenge in designing communication protocols in wireless networks. Most of the previous works had focused on the internal node changes (e.g., mobility, arrival, or departure) and not considered the effect of external environmental change. However, the external environmental change, in general, is a more complex phenomenon that can impede nodes from successful communication, implying the protocols of the previous dynamic models do not work well in practice. In this paper, we give an algorithm for distributed broadcasting in a more general model with fully dynamic wireless networks, called FD-Broadcast. Specifically, we present a fully dynamic model which allows node mobility and churns (due to node arrivals/departure) and external environmental change. In contrast to the previous works on dynamic networks, our model defines the full dynamicity in terms of localized topological changes of each node and can tolerate some external environmental change. The external environment changes are captured by the random jamming method. We show that FD-Broadcast can achieve broadcasting in$O(D_{S})$rounds with a high probability guarantee under the assumption of constant dynamic rate in the SINR model, where$D_{S}$is the dynamic diameter, a parameter proposed to depict the complexity of dynamic broadcasting. Moreover, the lower bound of dynamic broadcasting is proved to be$\Omega(D_{S})$, thus, FD-Broadcast is asymptotically optimal with high probability.