Search

Community search (CS) aims at personalized subgraph discovery which is the key to understanding the organisation of many real-world networks. CS in undirected networks has attracted significant attention from researchers, including many solutions for various cohesive subgraph structures and for different levels of dynamism with edge insertions and deletions, while they are much less considered for directed graphs. In this paper, we propose incremental solutions of CS based on the D-truss in dynamic directed graphs, where the D-truss is a cohesive subgraph structure defined based on two types of triangles in directed graphs. We first analyze the theoretical boundedness of D-truss given edge insertions and deletions, then we present basic single-update algorithms. To improve the efficiency, we propose an order-based D-Index, associated batchupdate algorithms and a fully-dynamic query algorithm. Our extensive experiments on real-world graphs show that our proposed solution achieves a significant speedup compared to the SOTA solution, the scalability over updates is also verified.

Owing to its nature of scalability and privacy by design, federated learning (FL) has received increasing interest in decentralized deep learning. FL has also facilitated recent research on upscaling and privatizing personalized recommendation services, using on-device data to learn recommender models locally. These models are then aggregated globally to obtain a more performant model while maintaining data privacy. Typically, federated recommender systems (FRSs) do not take into account the lack of resources and data availability at the end-devices. In addition, they assume that the interaction data between users and items is i.i.d. and stationary across end-devices (i.e., users), and that all local recommender models can be directly averaged without considering the user’s behavioral diversity. However, in real scenarios, recommendations have to be made on end-devices with sparse interaction data and limited resources. Furthermore, users’ preferences are heterogeneous and they frequently visit new items. This makes their personal preferences highly skewed, and the straightforwardly aggregated model is thus ill-posed for such non-i.i.d. data. In this article, we propose Resource Efficient Federated Recommender System (ReFRS) to enable decentralized recommendation with dynamic and diversified user preferences. On the device side, ReFRS consists of a lightweight self-supervised local model built upon the variational autoencoder for learning a user’s temporal preference from a sequence of interacted items. On the server side, ReFRS utilizes a scalable semantic sampler to adaptively perform model aggregation within each identified cluster of similar users. The clustering module operates in an asynchronous and dynamic manner to support efficient global model update and cope with shifting user interests. As a result, ReFRS achieves superior performance in terms of both accuracy and scalability, as demonstrated by comparative experiments on real datasets.

Uncertain butterflies are one of, if not the, most important graphlet structures on uncertain bipartite networks. In this paper, we examine the uncertain butterfly structure (in which the existential probability of the graphlet is greater than or equal to a threshold parameter), as well as the global Uncertain Butterfly Counting Problem (to count the total number of these instances over an entire network). To solve this task, we propose a non-trivial exact baseline (UBFC), as well as an improved algorithm (IUBFC) which we show to be faster both theoretically and practically. We also design two sampling frameworks (UBS and PES) which can sample either a vertex, edge or wedge from the network uniformly and estimate the global count quickly. Furthermore, a notable butterfly-based community structure which has been examined in the past is the k-bitruss. We adapt this community structure onto the uncertain bipartite graph setting and introduce the Uncertain Bitruss Decomposition Problem (which can be used to directly answer any k-bitruss search query for any k). We then propose an exact algorithm (UBitD) to solve our problem with three variations in deriving the initial uncertain support. Using a range of networks with different edge existential probability distributions, we validate the efficiency and effectiveness of our solutions. © 2023, The Author(s).

Online social networks have greatly facilitated our lives but have also propagated the spreading of rumours. Traditional works mostly find rumors from content, but content can be strategically manipulated to evade such detection, making these methods brittle. To improve the accuracy and robustness of rumor detection, we propose to integrate and exploit the content, propagation structure, and temporal relations because information in the networks always spreads dynamically with significant structures. In this paper, we propose a novel rumor detection framework in online temporal networks via structure learning. Specifically, to exploit the propagation structure, we propose a novel hyperedge walking strategy on a meta-hyperedge graph to learn the representations of sub-structures in the networks. Then a hyperedge expansion method is proposed to generate more global structural features. The expanded hyperedges are more hierarchical, making the learned structural embeddings more expressive. To make full use of content, we design a hypergraph learning model using hyperedge expansion to fuse node content with structural features and generate comprehensive representations for the entire graph. To exploit temporal relations, we design a masked temporal attention unit for learning the evolving patterns of the network. Extensive evaluations with six state-of-the-art baselines on two real-world datasets demonstrate the superiority of our solution. IEEE

Bipartite graphs are naturally used to model relationships between two different types of entities. On bipartite graphs, maximum biclique search is a fundamental problem that aims to find the complete bipartite subgraph (biclique) with the maximum number of edges and is widely adopted for many applications such as anomaly detection in E-commerce and social network analysis. However, maximum biclique search only identifies the biclique whose size is globally maximum, whereas fast microscopic (personalized) analysis is needed in many real-world scenarios. For instance, when a suspected user is identified in an E-commerce network (e.g., a user-product network), it is important to quickly find the anomalous group containing the user and send the group of users for further human expert investigation. To fill this research gap, for the first time, we study the efficient personalized maximum biclique search problem, which aims to find the maximum biclique containing a specific query vertex in real-time. Apart from online computation algorithms, we explore index-based approaches and propose the PMBC-Index. With the PMBC-Index, the query algorithm is up to five orders of magnitude faster than the baseline algorithms. Furthermore, effective pruning strategies and parallelization techniques are devised to support efficient index construction. Extensive experiments on 10 real-world graphs validate both the effectiveness and the efficiency of our proposed techniques.

Mining cohesive subgraphs on bipartite graphs is an important task. The k-bitruss is one of many popular cohesive subgraph models, which is the maximal subgraph where each edge is contained in at least k butterflies. The bitruss decomposition problem is to find all k-bitrusses for k ≥ 0. Dealing with large graphs is often beyond the capability of a single machine due to its limited memory and computational power, leading to a need for efficiently processing large graphs in a distributed environment. However, all current solutions are for a single machine and a centralized environment, where processors can access the graph or auxiliary indexes randomly and globally. It is difficult to directly deploy such algorithms on a shared-nothing model. In this paper, we propose distributed algorithms for bitruss decomposition. We first propose SC-HBD as the baseline, which uses H-function to define bitruss numbers and computes them iteratively to a fix point in parallel. We then introduce a subgraph-centric peeling method SC-PBD, which peels edges in batches over different butterfly complete subgraphs. We then introduce local indexes on each fragment, study the butterfly-aware edge partition problem including its hardness, and propose an effective partitioner. Finally we present the bitruss butterfly-complete subgraph concept, and divide and conquer DC-BD method with optimization strategies. Extensive experiments show the proposed methods solve graphs with 30 trillion butterflies in 2.5 hours, while existing parallel methods under shared-memory model fail to scale to such large graphs. © 2022, VLDB Endowment.

In this work we examine the problem of finding large, diverse communities on graphs where the users are separated into distinct groups. More specifically, this work considers diversity to be the inclusion of users from multiple groups as opposed to homogeneous communities in which the majority of users are from one group. We design and propose the k*-Partite Clique (and the edge-maximum k*-Partite Clique Problem) which modifies the k-Partite Clique structure as a means to capture these large, diverse communities in a way that does not currently exist. We then design a non-trivial baseline enumeration algorithm, which is further improved via heuristics to significantly reduce the running time whilst avoiding excessive memory requirements. Moreover, we propose a core as well as a truss structure for the k-Partite environment aimed at finding the edge-maximum k*-Partite Clique structure on the network. Comprehensive experiments on real-world datasets verify both the effectiveness of the k*-Partite Clique at finding diverse communities as well as the efficiency of the proposed heuristics to our algorithms compared to reasonable baselines.