Abstract Hypergraph decomposition is a fundamental problem in hypergraph analysis which breaks down hypergraphs into cohesive subgraphs and functional units with dense interactions. Hyperedge intersections and overlaps capture the unique property of shared elements (vertices) between groups (hyperedges) in hypergraphs, revealing cohesive substructures not apparent when focusing solely on individual connections. Despite the significance of hyperedge overlap as a measure of hypergraph cohesiveness, existing models for hypergraph decomposition fail to capture this feature. In this paper, we study the problem of hypergraph decomposition with intersection bounds. We propose the ( k , s )-core, a new cohesive subgraph model incorporating both a vertex degree constraint k and a hyperedge intersection constraint s . This model includes two types: (1) strong ( k , s )-cores, where connected hyperedges share at least s vertices, enforcing strong hyperedge overlap, and (2) weak ( k , s )-cores, where hyperedges are connected through s -walks, allowing for a looser overlap. We prove that our definition of ( k , s )-cores exhibits uniqueness and hierarchical properties. Based on the properties, we develop two decomposition algorithms: a bottom-up algorithm for strong ( k , s )-cores, which uses a heuristic hyperedge removal mechanism to maintain consistent decomposition results and employs a union-find data structure for efficient connectivity identification, and a top-down algorithm for weak ( k , s )-cores that preserves the subgraph containment relationship. Our algorithms achieve traversal efficiency by processing each hyperedge in the hypergraph only once. Additionally, all ( k , s )-cores can be efficiently stored with minimal memory overhead. Comprehensive experiments and case studies show that the ( k , s )-core model outperforms existing methods in capturing cohesive subgraphs with overlaps in hypergraphs. Furthermore, the proposed algorithms demonstrate high efficiency and scalability, making them well-suited for real-world hypergraphs.

Community search, which finds cohesive subgraphs containing given query vertices, has attracted much attention in decades. On attributed graphs, when considering the fairness of members' attributes in a community, the cohesiveness constraint of a clique is too strong, which often causes no fair clique based communities can be found. Thus, in this paper, we use the k-truss model, which is a relaxation of the clique but whose members have large engagement and high tie strength, to describe fair communities, namely fair k-truss communities (FTC) and anchored fair k-truss communities (AFTC, using anchored vertices to help satisfying the fairness constraint). We formulate the FTC and AFTC search problems to find the FTC or AFTC containing a given query vertex$q$which has the largest$k$and the smallest diameter. We prove the hardness of both problems. We develop several greedy algorithms and acceleration strategies to solve FTC and AFTC search problems. Experiments on 8 real-world networks show the significance of our FTC and AFTC models, and high performance of our algorithms and acceleration strategies.

The InterPlanetary File System (IPFS) is a prominent decentralized storage solution; however, it struggles with performance issues. To address this challenge, the IPFS team has patched a series of centralized components, resulting in improved performance while giving more significant roles to specific entities. Balancing speed and decentralization has always posed a complex dilemma for storage systems. In this paper, we conduct a series of experiments and analyses to identify the performance advantages and constraints associated with the IPFS decentralized protocol. Based on thorough analysis, we propose a novel scheme named XIPFS to optimize IPFS. This scheme includes facilitating parallel block exchange across multiple nodes, refining content Publication strategies, and improving node selection algorithms for content routing. Our goal is to maximize the benefits of decentralized multi-source parallel downloading while minimizing the negative impact of decentralized indexing on execution time. Compared to previous approaches, the proposed optimizations are lightweight and fully compatible with the decentralized protocol, enabling autonomous execution and utility realization at each node. Experimental results demonstrate that XIPFS significantly improves node performance without compromising decentralization.

Exploring the hierarchical structure of graphs presents notable advantages for graph analysis, revealing insights ranging from individual vertex behavior to community distribution and overall graph stability. This paper studies hierarchical structures within hypergraphs, where a hyperedge can connect multiple vertices. We observed that directly extending hierarchical frameworks from pairwise graphs to hypergraphs overlooks high-order interactions and can result in either high computational complexity or sparse hierarchy structure. To address this challenge, we introduce a dual-layer hypergraph hierarchy consisting of a primary hierarchy and a secondary hierarchy, enabling the construction of a refined hypergraph hierarchy in linear time. The dual-layer hierarchy establishes a global hierarchy based on vertex cohesion, utilizing vertex-induced subhypergraphs, and a local hierarchy based on hyperedge containment, employing edge-induced subhypergraphs. The combination of global and local hierarchy mitigates the homogeneity and sparsity issues inherent in single-layer hierarchies, allowing more effective modeling of high-order interactions. Furthermore, we propose an efficient hierarchical construction algorithm by leveraging a novel hyperedge-based disjoint set to identify connected subhypergraphs. Additionally, to optimize the local hierarchy further and prevent the emergence of excessively redundant levels, we introduce a compact local hierarchy by defining a restricted subgraph metric to eliminate redundancy caused by large-sized hyperedges. Empirical studies on real-world hypergraphs demonstrate the effectiveness of our approach.

Fixed-point decimal operations in databases with arbitrary-precision arithmetic refer to the ability to store and operate decimal fraction numbers with an arbitrary length of digits. This type of operation has become a requirement for many applications, including scientific databases, financial data processing, geometric data processing, and cryptography. However, the state-of-the-art fixed-point decimal technology either provides high performance for low-precision operations or supports arbitrary-precision arithmetic operations at low performance. In this paper, we present a design and implementation of a framework called UltraPrecise which supports arbitrary-precision arithmetic for databases on GPU, aiming to gain high performance for arbitrary-precision arithmetic operations. We build our framework based on the just-in-time compilation technique and optimize its performance via data representation design, PTX acceleration, and expression scheduling. UltraPrecise achieves comparable performance to other high-performance databases for low-precision arithmetic operations. For high-precision, we show that UltraPrecise consistently outperforms existing databases by two orders of magnitude, including workloads of RSA encryption and trigonometric function approximation.

We study federated unlearning, a novel problem to eliminate the impact of specific clients or data points on the global model learned via federated learning (FL). This problem is driven by the right to be forgotten and the privacy challenges in FL. We introduce a new framework for exact federated unlearning that meets two essential criteria:communication efficiencyandexact unlearning provability.To our knowledge, this is the first work to tackle both aspects coherently. We start by giving a rigorous definition ofexactfederated unlearning, which guarantees that the unlearned model is statistically indistinguishable from the one trained without the deleted data. We then pinpoint the key property that enables fast exact federated unlearning: total variation (TV) stability, which measures the sensitivity of the model parameters to slight changes in the dataset. Leveraging this insight, we develop a TV-stable FL algorithm called FATS, which modifies the classical FedAvg algorithm for TV Stability and employs local SGD with periodic averaging to lower the communication round. We also design efficient unlearning algorithms for FATS under two settings: client-level and sample-level unlearning. We provide theoretical guarantees for our learning and unlearning algorithms, proving that they achieve exact federated unlearning with reasonable convergence rates for both the original and unlearned models. We empirically validate our framework on 6 benchmark datasets, and show its superiority over state-of-the-art methods in terms of accuracy, communication cost, computation cost, and unlearning efficacy.

Betweenness centrality (BC), a classic measure which quantifies the importance of a vertex to act as a communication "bridge" between other vertices in the network, is widely used in many practical applications. With the advent of large heterogeneous information networks (HINs) which contain multiple types of vertices and edges like movie or bibliographic networks, it is essential to study BC computation on HINs. However, existing works about BC mainly focus on homogeneous networks. In this paper, we are the first to study a specific type of vertices' BC on HINs, e.g., find which vertices with typeAare important bridges to the communication between other vertices also with typeA?We advocate a meta path-based BC framework on HINs and formalize both coarse-grained and fine-grained BC (cBC and fBC) measures under the framework. We propose a generalized basic algorithm which can apply to computing not only cBC and fBC but also their variants in more complex cases. We develop several optimization strategies to speed up cBC or fBC computation by network compression and breadth-first search directed acyclic graph (BFS DAG) sharing. Experiments on several real-world HINs show the significance of cBC and fBC, and the effectiveness of our proposed optimization strategies.

Next point-of-interest (POI) recommendation has been a hot research topic, which enables new paradigms for kinds of location-based services in real-world scenarios. Due to the privacy concerns and rigorous data regulations, federated learning provides a distributed learning framework to collaboratively train the recommendation model without sharing the highly sensitive POI data with others. However, there exist two main challenges, namelylocation noise, andbalance between personalization and knowledge sharing, seriously restrict the development of the federated next POI recommendation. To this end, in this work, we propose an adaptive clustering based personalized federated learning framework for next POI recommendation with location noise, namedCPF-POI, to address the above challenges. In detail, within the local client, a location recovery module can efficiently remove noises under the given assumption from the noisy POI data in which the recovery error bound can be theoretically proved. Then, within the parameter server, an adaptive clustering scheme is proposed to capture the internal relatedness among all clients to augment positive knowledge sharing. In order to make a balance between personalization and knowledge sharing under personalized federated learning framework, we design an alternative optimization process between clustering similar clients and minimizing local personalized loss functions. Finally, extensive experiments are conducted on two diverse real-world datasets to show the advantages ofCPF-POIover state-of-the-art methods. improvement across all metrics on average.

The robust multivariate time series anomaly detection can facilitate intelligent decisions and timely maintenance in various kinds of monitor systems. However, the robustness is highly restricted by the stochasticity in multivariate time series, which is summarized astemporal stochasticityandspatial stochasticityspecifically. In this paper, we explicitly model the temporal stochasticity variables and the latent graph relationship variables into a unified graphical framework, which can achieve better robustness to dynamicity from both the spatial and temporal perspective. First, within the spatial encoder, every connection exists or not is modeled as a binary stochastic variable, and the graph structure can be learnt automatically. Then, the temporal encoder would embed the highly structured time series into latent stochastic variables to capture both complex temporal dependencies and neighbors information. Moreover, we design a history-future combined anomaly score mechanism with both reconstruction decoder and forecasting decoder to improve the anomaly detection performance. By weighting the historical anomaly factor, the future anomaly factor, and the prediction error of current timestamp, the anomaly detection at current timestamp could be more sensitive to anomaly detection. Finally, extensive experiments on three publicly available anomaly detection datasets demonstrate our proposed method can achieve the best performance in terms of recall and F1 compared with state-of-the-arts baselines.

Vertex engagement has extraordinary significance for social resilience and network stability. There have been lots of existing work studying this fundamental problem in pairwise graphs, but in the more generalized hypergraphs, it has not been well explored, due to the great challenges of sparsity, complex connectivity and dynamicity of hypergraphs. In this work, we initialize the study of the vertex engagement problem in hypergraphs. Based on the observation that the engagement of vertices in hypergraphs needs to consider two critical parameters, group engagement and neighbor engagement, we propose a vertex engagement model integrating the merits of these two measures, called constrained core, to address the ineffectiveness and incomprehensiveness caused by just using a single engagement factor. By giving an algorithm for the constrained core decomposition, we show that the constrained core number of vertices can be computed in linear time. Furthermore, by showing a localized property of contained core, efficient maintenance algorithms for updating the constrained core number of vertices in dynamic hypergraphs are proposed, to avoid the large amount of redundant computations caused by the decomposition from scratch. Extensive experiments conducted on real-world hypergraphs well exhibit the effectiveness of our model and the efficiency of the proposed algorithms.

Due to the privacy concerns and rigorous data regulations, dynamic treatment regimes across hospitals have become increasingly difficult. Fortunately, federated learning provides a distributed learning framework to collaboratively train the model without sharing the highly sensitive electronic health record (EHR) data with others. However, there exist two main challenges, namely data quality discrepancy, and heterogeneous data distribution, which seriously restrict the development of federated dynamic treatment regimes. To this end, we develop a global data quality aware dynamic treatment regime based on hierarchical federated reinforcement learning across different hospitals. In detail, we first quantify data quality in EHR using immediate health status changes, which are then utilized as rewards to encourage the high-quality treatment actions in the offline actor-critic reinforcement learning model. Within the parameter server, an online reinforcement learning based clustering scheme is proposed to capture the internal similarities to augment the positive knowledge transfer of high-quality hospitals while neglecting the heterogeneity. Extensive experiments are conducted on two diverse real-world datasets to show the advantages of DFR-DTR over state-of-the-art baselines.

In this paper, we propose an adaptive learning paradigm for resource-constrained cross-device federated learning, in which heterogeneous local submodels with varying resources can be jointly trained to produce a global model. Different from existing studies, the submodel structures of different clients are formed by arbitrarily assigned neurons according to their local resources. Along this line, we first design a general resource-adaptive federated learning algorithm, namely RA-Fed, and rigorously prove its convergence with asymptotically optimal rate O(1/√Γ*TQ) under loose assumptions. Furthermore, to address both submodels heterogeneity and data heterogeneity challenges under non-uniform training, we come up with a new server aggregation mechanism RAM-Fed with the same theoretically proved convergence rate. Moreover, we shed light on several key factors impacting convergence, such as minimum coverage rate, data heterogeneity level, submodel induced noises. Finally, we conduct extensive experiments on two types of tasks with three widely used datasets under different experimental settings. Compared with the state-of-the-arts, our methods improve the accuracy up to 10% on average. Particularly, when submodels jointly train with 50% parameters, RAM-Fed achieves comparable accuracy to FedAvg trained with the full model.

With the raised privacy concerns and rigorous data regulations, federated learning has become a hot collaborative learning paradigm for the recommendation model without sharing the highly sensitive POI data. However, the time-sensitive, heterogeneous, and limited POI records seriously restrict the development of federated POI recommendation. To this end, in this paper, we design the fine-grained preference-aware personalized federated POI recommendation framework, namely PrefFedPOI, under extremely sparse historical trajectories to address the above challenges. In details, PrefFedPOI extracts the fine-grained preference of current time slot by combining historical recent preferences and periodic preferences within each local client. Due to the extreme lack of POI data in some time slots, a data amount aware selective strategy is designed for model parameters uploading. Moreover, a performance enhanced clustering mechanism with reinforcement learning is proposed to capture the preference relatedness among all clients to encourage the positive knowledge sharing. Furthermore, a clustering teacher network is designed for improving efficiency by clustering guidance. Extensive experiments are conducted on two diverse real-world datasets to demonstrate the effectiveness of proposed PrefFedPOI comparing with state-of-the-arts. In particular, personalized PrefFedPOI can achieve 7% accuracy improvement on average among data-sparsity clients.

The study of graph kernels has been an important area of graph analysis, which is widely used to solve the similarity problems between graphs. Most of the existing graph kernels consider either local or global properties of the graph, and there are few studies on multiscale graph kernels. In this article, the authors propose a framework for graph kernels based on truss decomposition, which allows multiple graph kernels and even any graph comparison algorithms to compare graphs at different scales. The authors utilize this framework to derive variants of five graph kernels and compare them with the corresponding basic graph kernels on graph classification tasks. Experiments on a large number of benchmark datasets demonstrate the effectiveness and efficiency of the proposed framework.

Differential privacy provides strong privacy preservation guarantee in information sharing. As social network analysis has been enjoying many applications, it opens a new arena for applications of differential privacy. This article presents a comprehensive survey connecting the basic principles of differential privacy and applications in social network analysis. We concisely review the foundations of differential privacy and the major variants. Then, we discuss how differential privacy is applied to social network analysis, including privacy attacks in social networks, models of differential privacy in social network analysis, and a series of popular tasks, such as analyzing degree distribution, counting subgraphs and assigning weights to edges. We also discuss a series of challenges for future work.

In this article, we study a distributed privacy-preserving learning problem in social networks with general topology. The agents can communicate with each other over the network, which may result in privacy disclosure, since the trustworthiness of the agents cannot be guaranteed. Given a set of options which yield unknown stochastic rewards, each agent is required to learn the best one, aiming at maximizing the resulting expected average cumulative reward. To serve the above goal, we propose a four-staged distributed algorithm which efficiently exploits the collaboration among the agents while preserving the local privacy for each of them. In particular, our algorithm proceeds iteratively, and in every round, each agent i) randomly perturbs its adoption for the privacy-preserving purpose, ii) disseminates the perturbed adoption over the social network in a nearly uniform manner through random walking, iii) selects an option by referring to the perturbed suggestions received from its peers, and iv) decides whether or not to adopt the selected option as preference according to its latest reward feedback. Through solid theoretical analysis, we quantify the trade-off among the number of agents (or communication overhead), privacy preserving and learning utility. We also perform extensive simulations to verify the efficacy of our proposed social learning algorithm.

Searching for$k$-cliques in graphs has been an important problem in graph analysis due to its large number of applications. Previously, finding$k$-cliques in weighted graphs aimed at finding cliques with the largest sum of weight (with no distinction between the edge or the vertex weights), usually called the sum model. However, the algorithms under the sum model may result in solutions consisting of low-weight vertices or edges (outliers). To address this issue, we propose a new model named maximal$(S, C, K)$-clique in weighted graphs and study the problem of maximal ($S, C, K$)-clique search (MCS). We first propose an enumeration-based algorithm MCSE, which checks every$k$-clique to identify the maximal ($S, C, K$)-clique. To improve the efficiency, we further propose two improved algorithms MCSP and MCSC. Instead of checking every possible$k$-clique, MCSP focuses on ($S, C$) values that cannot be dominated and obtains the maximal$(S, C, K)$-cliques directly based on these values. MCSC is devised by further optimizing MCSP based on some key observations on maximal cliques and cliques’ nesting property. We also propose two index structures, BCS-Index and ICS-Index, to achieve optimal query. The former stores all maximal$(S, C, K)$-cliques, while the latter uses the clique's nesting property to reduce the space cost of index construction. Extensive experiments conducted on six real graphs demonstrate the efficiency and effectiveness of our proposed algorithms.

In this paper, we study exact hypercore maintenance in large-scale dynamic hypergraphs. A hypergraph, whose hyperedges may contain a set of vertices rather than two vertices in pairwise graphs, can represent complex interactions in more sophisticated applications. However, the exponential number of hyperedges incurs unaffordable costs to recompute the hypercore number of vertices and hyperedges when updating a hypergraph. This motivates us to propose an efficient approach for exact hypercore maintenance with the intention of significantly reducing the hypercore updating time comparing with recomputation approaches. The proposed algorithms can pinpoint the vertices and hyperedges whose hypercore numbers have to be updated by only traversing a small sub-hypergraph. Extensive experiments on real-world and temporal hypergraphs demonstrate the superiority of our algorithms in terms of efficiency.

With distinct privacy protection advantages, federated recommendation is becoming increasingly feasible to store data locally in devices and federally train recommender models. However, previous work on federated recommender systems does not take full account of the limitations of storage, RAM, energy and communication bandwidth in the mobile environment. Their model scales are too big to run easily in mobile devices. Moreover, existing federated recommenders need to fine-tune recommendation models in each device, which makes them hard to effectively exploit collaborative filtering (CF) information among users/devices.