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.

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.

In recent years, fake news has been a primary concern as it plays a significant role in influencing the political, economic, and social spheres. The scientific community has proposed several solutions to detect such fraudulent information. However, such solutions are unsuitable for social media posts since they cannot extract sufficient information from one-line textual and graphical content or are highly dependent on prior knowledge, which may be unavailable in the case of unprecedented events (e.g., breaking news).

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.

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.

Sequential recommendations aim to capture users’ preferences from their historical interactions so as to predict the next item that they will interact with. Sequential recommendation methods usually assume that all items in a user’s historical interactions reflect her/his preferences and transition patterns between items. However, real-world interaction data is imperfect in that (i) users might erroneously click on items, i.e., so-called misclicks on irrelevant items, and (ii) users might miss items, i.e., unexposed relevant items due to inaccurate recommendations.

Deep Learning (DL) has been widely adopted in almost all domains, from threat recognition to medical diagnosis. Albeit its supreme model accuracy, DL imposes a heavy burden on devices as it incurs overwhelming system overhead to execute DL models, especially on Internet-of-Things (IoT) and edge devices. Collaborative inference is a promising approach to supporting DL models, by which the data owner (the victim) runs the first layers of the model on her local device and then a cloud provider (the adversary) runs the remaining layers of the model. Compared to offloading the entire model to the cloud, the collaborative inference approach is more data privacy-preserving as the owner’s model input is not exposed to outsiders. However, we show in this paper that the adversary can restore the victim’s model input by exploiting the output of the victim’s local model. Our attack is dubbed Ginver 1: Generative model inversion attacks against collaborative inference. Once trained, Ginver can infer the victim’s unseen model inputs without remaking the inversion attack model and thus has the generative capability. We extensively evaluate Ginver under different settings (e.g., white-box and black-box of the victim’s local model) and applications (e.g., CIFAR10 and FaceScrub datasets). The experimental results show that Ginver recovers high-quality images from the victims.

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.

A large amount of high-dimensional and heterogeneous data appear in practical applications, which are often published to third parties for data analysis, recommendations, targeted advertising, and reliable predictions. However, publishing these data may disclose personal sensitive information, resulting in an increasing concern on privacy violations. Privacy-preserving data publishing has received considerable attention in recent years. Unfortunately, the differentially private publication of high dimensional data remains a challenging problem. In this paper, we propose a differentially private high-dimensional data publication mechanism (DP2-Pub) that runs in two phases: a Markov-blanket-based attribute clustering phase and an invariant post randomization (PRAM) phase. Specifically, splitting attributes into several low-dimensional clusters with high intra-cluster cohesion and low inter-cluster coupling helps obtain a reasonable allocation of privacy budget, while a double-perturbation mechanism satisfying local differential privacy facilitates an invariant PRAM to ensure no loss of statistical information and thus significantly preserves data utility. We also extend our DP2-Pub mechanism to the scenario with a semi-honest server which satisfies local differential privacy. We conduct extensive experiments on four real-world datasets and the experimental results demonstrate that our mechanism can significantly improve the data utility of the published data while satisfying differential privacy.

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.

User response prediction, which aims to predict the probability that a user will provide a predefined positive response in a given context such as clicking on an ad or purchasing an item, is crucial to many industrial applications such as online advertising, recommender systems, and search ranking. For these tasks and many other machine learning tasks, an indispensable part of success is feature engineering, where cross features are a significant type of feature transformations. However, due to the high dimensionality and super sparsity of the data collected in these tasks, handcrafting cross features is inevitably time expensive. Prior studies in predicting user response leveraged the feature interactions by enhancing feature vectors with products of features to model second-order or high-order cross features, either explicitly or implicitly. However, these existing methods can be hindered by not learning sufficient cross features due to model architecture limitations or modeling all high-order feature interactions with equal weights. Different features should contribute differently to the prediction, and not all cross features are with the same prediction power.

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.

Quality control in crowdsourcing is challenging due to the heterogeneous nature of the workers. The state-of-the-art solutions attempt to address the issue from the technical perspective, which may be costly because they function as an additional procedure in crowdsourcing. In this paper, an economics based idea is adopted to embed quality control into the crowdsourcing process, where the requestor can take advantage of the market power to stimulate the workers for submitting high-quality jobs. Specifically, we employ two sequential games to model the interactions between the requestor and the workers, with one considering binary strategies while the other taking continuous strategies. Accordingly, two incentive algorithms for improving the job quality are proposed to tackle the sequential crowdsourcing dilemma problem. Both algorithms are based on a sequential zero-determinant (ZD) strategy modified from the classical ZD strategy. Such a revision not only provides a theoretical basis for designing our incentive algorithms, but also enlarges the application space of the classical ZD strategy itself. Our incentive algorithms have the following desired features: 1) they do not depend on any specific crowdsourcing scenario; 2) they leverage economics theory to train the workers to behave nicely for better job quality instead of filtering out the unprofessional workers; 3) no extra costs are incurred in a long run of crowdsourcing; and 4) fairness is realized as even the requestor (the ZD player), who dominates the game, cannot increase her utility by arbitrarily penalizing any innocent worker.

This paper targets the identification of outlying sensors (that is, outlying reading sensors) and the detection of the reach of events in sensor networks. Typical applications include the detection of the transportation front line of some vegetation or animalcule's growth over a certain geographical region. We propose and analyze two novel algorithms for outlying sensor identification and event boundary detection. These algorithms are purely localized and, thus, scale well to large sensor networks. Their computational overhead is low, since only simple numerical operations are involved. Simulation results indicate that these algorithms can clearly detect the event boundary and can identify outlying sensors with a high accuracy and a low false alarm rate when as many as 20 percent sensors report outlying readings. Our work is exploratory in that the proposed algorithms can accept any kind of scalar values as inputs-a dramatic improvement over existing work, which takes only 0/1 decision predicates. Therefore, our algorithms are generic. They can be applied as long as "events" can be modeled by numerical numbers. Though designed for sensor networks, our algorithms can be applied to the outlier detection and regional data analysis in spatial data mining.