Due to the power of learning representations from unlabeled graphs, graph contrastive learning (GCL) has shown excellent performance in community detection tasks. Existing GCL-based methods on the community detection usually focused on learning attribute representations of individual nodes, which, however, ignores structure semantics of communities (e.g., nodes in the same community should be structurally cohesive). Therefore, in this paper, we consider the community detection under the community structure semantics and propose an effective framework for graph contrastive learning under structure semantics (GCLS2) to detect communities. To seamlessly integrate interior dense and exterior sparse characteristics of communities with our contrastive learning strategy, we employ classic community structures to extract high-level structural views and design a structure semantic expression module to augment the original structural feature representation. Moreover, we formulate the structure contrastive loss to optimize the feature representation of nodes, which can better capture the topology of communities. To adapt to large-scale networks, we design a high-level graph partitioning (HGP) algorithm that minimizes the community detection loss for GCLS2 online training. It is worth noting that we prove a lower bound on the training of GCLS2 from the perspective of the information theory, explaining why GCLS2 can learn a more accurate representation of the structure. Extensive experiments have been conducted on various real-world graph datasets and confirmed that GCLS2 outperforms nine state-of-the-art methods, in terms of the accuracy, modularity, and efficiency of detecting communities.

As a promising privacy-aware collaborative model training paradigm, Federated Learning (FL) is becoming popular in the design of distributed recommender systems. However, Federated Recommender Systems (FedRecs) greatly suffer from two major problems: i) extremely high communication overhead due to massive item embeddings involved in recommendation systems, and ii) intolerably low training efficiency caused by the entanglement of both heterogeneous network environments and client devices. Although existing methods attempt to employ various compression techniques to reduce communication overhead, due to the parameter errors introduced by model compression, they inevitably suffer from model performance degradation. To simultaneously address the above problems, this paper presents a communication-efficient FedRec framework named FedRAS, which adopts an action-sharing strategy to cluster the gradients of item embedding into a specific number of model updating actions for communication rather than directly compressing the item embeddings. In this way, the cloud server can use the limited actions from clients to update all the items. Since gradient values are significantly smaller than item embeddings, constraining the directions of gradients (i.e., the action space) introduces smaller errors compared to compressing the entire item embedding matrix into a reduced space. To accommodate heterogeneous devices and network environments, FedRAS incorporates an adaptive clustering mechanism that dynamically adjusts the number of actions. Comprehensive experiments on well-known datasets demonstrate that FedRAS can reduce the size of communication payloads by up to 96.88%, while not sacrificing recommendation performance within various heterogeneous scenarios. We have open-sourced FedRAS at https://github.com/mastlab-T3S/FedRAS.

In many real-world applications such as social network analysis, knowledge graph discovery, biological network analytics, and so on, graph data management has become increasingly important and has drawn much attention from the database community. While many graphs (e.g., Twitter, Wikipedia, etc.) are usually evolving over time, it is of great importance to study the continuous subgraph matching (CSM) problem, a fundamental, yet challenging, graph operator, which continuously monitors subgraph matching results over dynamic graphs with a stream of edge updates. To efficiently tackle the CSM problem, we carefully design a general CSM processing framework, based on novel DynamIc Vertex DomINance Embedding (DIVINE), which maps vertex neighborhoods into an embedding space to enable efficient subgraph matching and incremental maintenance under dynamic updates. Inspired by low pruning power for high-degree vertices, we propose a new degree grouping technique to decompose high-degree star patterns into groups of lower-degree star substructures, and devise degree-aware star substructure synopses (DAS 3 ) over embeddings of star substructure groups. We develop efficient algorithms to incrementally maintain dynamic graphs and answer CSM queries by traversing DAS 3 synopses and applying our designed vertex dominance and range pruning strategies. Through extensive experiments, we confirm the efficiency of our proposed DIVINE approach over both real and synthetic graphs.

For the past decades, the subgraph similarity search over a large-scale data graph has become increasingly important and crucial in many real-world applications, such as social network analysis, bioinformatics network analytics, knowledge graph discovery, and many others. While previous works on subgraph similarity search used various graph similarity metrics such as the graph isomorphism, graph edit distance, and so on, in this paper, we propose a novel problem, namely subgraph similarity search under aggregated neighbor difference semantics (S 3 AND), which identifies subgraphs g in a data graph G that are similar to a given query graph q by considering both keywords and graph structures (under new keyword/structural matching semantics). To efficiently tackle the S 3 AND problem, we design two effective pruning methods, keyword set and aggregated neighbor difference lower bound pruning , which rule out false alarms of candidate vertices/subgraphs to reduce the S 3 AND search space. Furthermore, we construct an effective indexing mechanism to facilitate our proposed efficient S 3 AND query answering algorithm. Through extensive experiments, we demonstrate the effectiveness and efficiency of our S 3 AND approach over both real and synthetic graphs under various parameter settings.

As a promising distributed machine learning paradigm, Federated Learning (FL) has attracted increasing attention to deal with data silo problems without compromising user privacy. By adopting the classic one-to-multi training scheme (i.e., FedAvg), where the cloud server dispatches one single global model to multiple involved clients, conventional FL methods can achieve collaborative model training without data sharing. However, since only one global model cannot always accommodate all the incompatible convergence directions of local models, existing FL approaches greatly suffer from inferior classification accuracy. To address this issue, we present an efficient FL framework named FedCross, which uses a novel multi-to-multi FL training scheme based on our proposed multi-model cross-aggregation approach. Unlike traditional FL methods, in each round of FL training, FedCross uses multiple middleware models to conduct weighted fusion individually. Since the middleware models used by FedCross can quickly converge into the same flat valley in terms of loss landscapes, the generated global model can achieve a well-generalization. Experimental results on various well-known datasets show that, compared with state-of-the-art FL methods, Fed Cross can significantly improve FL accuracy within both IID and non-IID scenarios without causing additional communication overhead.

In many real-world applications such as social network analysis and online marketing/advertising, community detection is a fundamental task to identify communities (subgraphs) in social networks with high structural cohesiveness. While previous works focus on detecting communities alone, they do not consider the collective influences of users in these communities on other user nodes in social networks. Inspired by this, in this paper, we investigate the influence propagation from some seed communities and their influential effects that result in the influenced communities. We propose a novel problem, named Top-L most Influential Community DEtection ($\text{Top}L$-ICDE) over social networks, which aims to retrieve top-$L$seed communities with the highest influences, having high structural cohesiveness, and containing user-specified query keywords. To efficiently tackle the$\text{Top}L$-ICDE problem, we design effective pruning strategies to filter out false alarms of seed communities and propose an effective index mechanism to facilitate efficient Top-$L$community retrieval. We develop an efficient$\text{Top}L$-ICDE answering algorithm by traversing the index and applying our proposed pruning strategies. We also formulate and tackle a variant of$\text{Top}L$-ICDE, named diversified top-L most influential community detection ($\text{Top}L$-ICDE), which returns a set of$L$diversified communities with the highest diversity score (i.e., collaborative influences by$L$communities). We prove that$\text{DTop}L$-ICDE is NP-hard, and propose an efficient greedy algorithm with our designed diversity score pruning. Through extensive experiments, we verify the efficiency and effectiveness of our proposed$\text{Top}L$-ICDE and$\text{DTop}L$-ICDE approaches over real/synthetic social networks under various parameter settings.

Although Federated Learning (FL) enables global model training across clients without compromising their raw data, due to the un- evenly distributed data among clients, existing Federated Averaging (FedAvg)-based methods suffer from the problem of low inference performance. Specifically, different data distributions among clients lead to various optimization directions of local models. Aggregat- ing local models usually results in a low-generalized global model, which performs worse on most of the clients. To address the above issue, inspired by the observation from a geometric perspective that a well-generalized solution is located in a flat area rather than a sharp area, we propose a novel and heuristic FL paradigm named FedMR (Federated Model Recombination). The goal of FedMR is to guide the recombined models to be trained towards a flat area. Unlike conventional FedAvg-based methods, in FedMR, the cloud server recombines collected local models by shuffling each layer of them to generate multiple recombined models for local training on clients rather than an aggregated global model. Since the area of the flat area is larger than the sharp area, when local models are located in different areas, recombined models have a higher probability of locating in a flat area. When all recombined models are located in the same flat area, they are optimized towards the same direction. We theoretically analyze the convergence of model recombination. Experimental results show that, compared with state-of-the-art FL methods, FedMR can significantly improve the inference accuracy without exposing the privacy of each client.

Large-scale streaming matrix multiplication is very common in various applications, sparking significant interest in develop efficient algorithms for approximate matrix multiplication (AMM) over streams. In addition, many practical scenarios require to process time-sensitive data and aim to compute matrix multiplication for most recent columns of the data matrices rather than the entire matrices, which motivated us to study efficient AMM algorithms over sliding windows. In this paper, we present two novel deterministic algorithms for this problem and provide corresponding error guarantees. We further reduce the space and time costs of our methods for sparse matrices by performing an approximate singular value decomposition which can utilize the sparsity of matrices. Extensive experimental results on both synthetic and real-world datasets validate our theoretical analysis and highlight the efficiency of our methods.

The classic problem of exact subgraph matching returns those subgraphs in a large-scale data graph that are isomorphic to a given query graph, which has gained increasing importance in many real-world applications such as social network analysis, knowledge graph discovery in the Semantic Web, bibliographical network mining, and so on. In this paper, we propose a novel and effective graph neural network (GNN)-based path embedding framework (GNN-PE), which allows efficient exact subgraph matching without introducing false dismissals. Unlike traditional GNN-based graph embeddings that only produce approximate subgraph matching results, in this paper, we carefully devise GNN-based embeddings for paths, such that: if two paths (and 1-hop neighbors of vertices on them) have the subgraph relationship, their corresponding GNN-based embedding vectors will strictly follow the dominance relationship. With such a newly designed property of path dominance embeddings, we are able to propose effective pruning strategies based on path label/dominance embeddings and guarantee no false dismissals for subgraph matching. We build multidimensional indexes over path embedding vectors, and develop an efficient subgraph matching algorithm by traversing indexes over graph partitions in parallel and applying our pruning methods. We also propose a cost-model-based query plan that obtains query paths from the query graph with low query cost. Through extensive experiments, we confirm the efficiency and effectiveness of our proposed GNN-PE approach for exact subgraph matching on both real and synthetic graph data.

Although Reinforcement Learning (RL) has achieved significant success in the Traffic Signal Control (TSC), most of them focus on the design of RL elements while the impact of the phase duration is neglected. Due to the lack of exploring dynamic phase duration, the overall performance and convergence rate of RL-based TSC approaches cannot be guaranteed, which may result in poor adaptability of RL methods to different traffic conditions. To address these issues, in this paper, we formulate a novel phase-duration-aware TSC (PDA-TSC) problem and propose an effective RL-based TSC approach, named MonitorLight. Our approach adopts a new traffic indicator, mixed pressure, which enables RL agents to simultaneously analyze the impacts of stationary and moving vehicles on intersections. Based on the observed mixed pressure of intersections, RL agents can autonomously determine whether or not to change the current signals in real-time. In addition, MonitorLight can adjust the control method for scenarios with different real-time requirements and achieve excellent results in different situations. Extensive experiments on both real-world and synthetic datasets demonstrate that MonitorLight outperforms the current state-of-the-art IPDALight by up to 2.84% and 5.71% in average vehicle travel time, respectively. Moreover, our method significantly speeds up the convergence, leading IPDALight by 36.87% and 34.58% in the start to converge episode and jumpstart performance, respectively.

To embrace the era of big data, there has been growing interest in designing distributed machine learning to exploit the collective computing power of the local computing nodes. Alternating Direction Method of Multipliers (ADMM) is one of the most popular methods. This method applies iterative local computations over local datasets at each agent and computation results exchange between the neighbors. During this iterative process, data privacy leakage arises when performing local computation over sensitive data. Although many differentially private ADMM algorithms have been proposed to deal with such privacy leakage, they still have to face many challenging issues such as low model accuracy over strict privacy constraints and requiring strong assumptions of convexity of the objective function. To address those issues, in this paper, we propose a differentially private robust ADMM algorithm (PR-ADMM) with Gaussian mechanism. We employ two kinds of noise variance decay schemes to carefully adjust the noise addition in the iterative process and utilize a threshold to eliminate the too noisy results from neighbors. We also prove that PR-ADMM satisfies dynamic zero-concentrated differential privacy (dynamic zCDP) and a total privacy loss is given by (∈, δ)-differential privacy. From a theoretical point of view, we analyze the convergence rate of PR-ADMM for general convex objectives, which is O(1/K) with K being the number of iterations. The performance of the proposed algorithm is evaluated on real-world datasets. The experimental results show that the proposed algorithm outperforms other differentially private ADMM based algorithms under the same total privacy loss.