Search

With the exponential growth of mobile devices and data traffic, mobile edge computing has become a promising technology, and the placement of edge servers plays a key role in providing efficient and low-latency services. In this paper, we investigate the issue of edge server placement and user allocation to reduce transmission delay between base stations and servers, and balance the workload of individual servers. To this end, we propose a graph clustering-based edge server placement model by fully considering the constraints such as the distance, coverage area and number of channels of base stations. The model mainly consists of a two-layer graph convolutional network (GCN) component and a differentiable version of K-means clustering component, which transforms the server placement problem into an end-to-end learning optimization problem on a graph. It trains the GCN network to achieve the best clustering results with the expectation of average delay and load balancing as the loss function to obtain the edge server placement and user assignment scheme. We conducted experiments based on the Shanghai Telecom dataset, and the results show the effectiveness of our approach in both latency reduction and load balancing. [ABSTRACT FROM AUTHOR]

Contrastive graph clustering (CGC) has emerged as a research hotspot in current studies, aiming to leverage the robust representational capability of contrastive learning to improve graph clustering performance. Recent works have shown that CGC can benefit from hard sample mining. However, we observe two primary shortcomings of existing CGC methods that limit further enhancements in clustering performance. Firstly, the widely used contrastive loss mistakenly classifies elements outside the cross-view diagonal as negatives, yielding numerous false negatives. Secondly, without explicit cluster-guiding, learned node embeddings become unsuitable for clustering tasks. To address these issues, we propose a novel CGC method by Enhanced hard sample mining and cluster-guiding (CGCEC). This method generates high-confidence pseudo-labels by clustering node embeddings during network training. Furthermore, we have designed a hard sample debiased mining loss that uses pseudo-labels to remove the false negative samples, repelling hard negatives while attracting hard positives, thus enhancing the discriminability of the learned embeddings. Additionally, we employ the encoder to transform node embeddings into semantic labels, promoting the network to learn node embeddings more suitable to clustering by matching semantic labels with pseudo-labels. To validate CGCEC’s effectiveness, we compare it with state-of-the-art graph clustering methods across six benchmark datasets. The experimental results substantiate the efficacy of our method and its superiority over competing approaches. [ABSTRACT FROM AUTHOR]

In this paper, we proposed VGASOM, a neural network approach for community detection. Community detection refers to discovering similar nodes in a graph that form a community having similar features or attributes as opposed to nodes from other communities. The proposed approach combines the capabilities of auto-encoder neural networks, specifically a Variational graph auto-encoder (VGAE) with self-organizing maps (SOM) clustering. VGAEs have achieved great success in learning the latent representation of graphs and therefore encoding them into lower-dimensional embeddings. The self-organizing map based on competitive learning is used to find communities in the graphs' embeddings obtained by the VGAE model which further reduces its dimensionality and divides the input space into clusters that correspond to the communities in the graph. We conducted experiments to evaluate our model compared to several baseline models, our model shows promising results for the community detection task. It outperforms the state-of-the-art methods by 3.29% in terms of the accuracy and 9% in terms of F1 metric. [ABSTRACT FROM AUTHOR]

Intelligent detection of the apparent defects of tunnel linings on the basis of deep learning has become a mainstream trend, and how to objectively diagnose the hazard level of tunnel defects via semantic segmentation images is the key to intelligent control of tunnel health. In this study, a tunnel lining defect image diagnosis method that uses graph neural networks is proposed. First, the binary images obtained by semantic segmentation are used as the data set, and quantitative parameters, such as crack length, maximum width, box dimension, and area density, are calculated according to the crack orientation and employed as graph node attributes. Second, the construction of graph data is based on the similarity of defect attributes. Third, clustering is completed using graph neural networks and K-means, and the number of clusters and danger levels of crack defects are reasonably determined. Last, a tunnel crack risk index is developed via partial least squares regression analysis, and the grading criteria for defect levels are established. Results show that the method is effective in extracting the key attributes of crack images and clustering them into different hazard levels, which is important for maintaining tunnel health. [ABSTRACT FROM AUTHOR]

Abstract With the exponential growth of mobile devices and data traffic, mobile edge computing has become a promising technology, and the placement of edge servers plays a key role in providing efficient and low-latency services. In this paper, we investigate the issue of edge server placement and user allocation to reduce transmission delay between base stations and servers, and balance the workload of individual servers. To this end, we propose a graph clustering-based edge server placement model by fully considering the constraints such as the distance, coverage area and number of channels of base stations. The model mainly consists of a two-layer graph convolutional network (GCN) component and a differentiable version of K-means clustering component, which transforms the server placement problem into an end-to-end learning optimization problem on a graph. It trains the GCN network to achieve the best clustering results with the expectation of average delay and load balancing as the loss function to obtain the edge server placement and user assignment scheme. We conducted experiments based on the Shanghai Telecom dataset, and the results show the effectiveness of our approach in both latency reduction and load balancing.

The problem of finding all shortest paths between vertices in a graph (APSP) has real-life applications in planning, communication, economics and many other areas. APSP problem can be solved using various algorithms, starting from Floyd-Warshall’s algorithm and ending with advanced, much faster blocked algorithms like Heterogeneous Blocked All-Pairs Shortest Path Algorithm designed to fully utilize underlying hardware resources and utilize inter-data relationships. In the paper, we propose a novel Blocked all-pairs Shortest Paths algorithm for Clustered Graphs (BSPCG) (in sequential and parallel forms) which utilizes the graph clustering information to significantly reduce the number of calculations by performing shortest paths search only though bridge vertices between clusters. We performed a set of comparing experiments for BSPCG and standard Blocked All-Pairs Shortest Path (BFW) algorithm on four randomly generated graphs of 4800 and 9600 vertices with different cluster configurations to determine the efficiency of calculation of paths passing through bridge vertices. All experiments were executed on a computer with two Intel Xeon E5-2620v4 processors (8 cores, 16 hardware threads and shared 20 MB L3 cache). In all the experiments the novel BSPCG algorithm outperformed the standard BFW algorithm. In single-threaded scenarios, BSPCG outperformed BFW up to 4.6 times on graphs of 4800 vertices and up to 2.7 times on graphs of 9600 vertices. In the multi-threaded scenarios, BSPCG also outperformed BFW up to times on graphs of 4800 vertices and up to 2.7 times on graphs of 9600 vertices. The proposed algorithm can be used in scenarios where clustering information stays intact or slightly modified based on the changes in graph and can be reused for future calculation of all-pairs shortest paths in the graph.

Data platforms with large dimensions, despite the opportunities they create, create many computational challenges. One of the problems of data with large dimensions is that most of the time, all the characteristics of the data are not important and vital to finding the knowledge that is hidden in them. These features can have a negative effect on the performance of the classification system. An important technique to overcome this problem is feature selection. During the feature selection process, a subset of primary features is selected by removing irrelevant and redundant features. In this article, a hierarchical algorithm based on the coverage solution will be presented, which selects effective features by using relationships between features and clustering techniques. This new method is named GCPSO, which is based on the optimization algorithm and selects the appropriate features by using the feature clustering technique. The feature clustering method presented in this article is different from previous algorithms. In this method, instead of using traditional clustering models, final clusters are formed by using the graphic structure of features and relationships between features. The UCI database has been used to evaluate the proposed method due to its extensive characteristics. The efficiency of the proposed model has also been compared with the feature selection methods based on the coverage solution that uses evolutionary algorithms in the feature selection process. The obtained results indicate that the proposed method has performed well in terms of choosing the optimal subset and classification accuracy on all data sets and in comparison with other methods. [ABSTRACT FROM AUTHOR]

The article introduces a new method for applying Quantum Clustering to graph structures. Quantum Clustering (QC) is a density-based unsupervised learning method that determines cluster centers by constructing a potential function. In this method, we develop the Graph Gradient Descent algorithm to find the centers of clusters for graph analysis. GPU parallelization is utilized for computing potential values. We also conducted comparative experiments on five widely used datasets and evaluated them using four indicators. The results show superior performance of our method. Finally, we discuss the influence of the crucial parameter σ on the experimental results. [ABSTRACT FROM AUTHOR]

Community detection is a fundamental yet important task for characterizing and understanding the structure of attributed graphs. Existing methods mainly focus on the structural tightness and attribute similarity among nodes in a community. However, grouping numerous semantically homogeneous nodes will result in information cocoons and thus reduce the robustness of community structure and the efficiency of node collaboration in real-world applications, such as recommendation systems and collaboration networks. Since nodes with closer connections tend to be more similar, finding communities with dense structures and diverse attributes poses great challenges to mining latent relationships between the graph structure and attribute distribution. To our best knowledge, very little research has been conducted to address this challenge. In this article, we propose a novel three-view graph attention neural networks (TvGANN) model to formally address the attribute diversity aware community detection problem. TvGANN reveals correlations between the graph structure and attributes distribution from the perspective of node organization, attribute co-occurrence, and the node-attribute interaction. It effectively captures structural features and attributes distribution by feeding a structural network and an attribute co-occurrence network into graph attention modules through the encoder–decoder framework. It also learns heterogeneous information by feeding a network into a meta-node attention module. Then, it fuzes the three modules and clusters the embedding representations through a Student's t-distribution approach, which iteratively refines the clustering results. The experiments show that our method not only improves the quality in dense community detection but also performs efficiently for attributed graphs. [ABSTRACT FROM AUTHOR]

Graph clustering is an essential task in data analysis. Recently, there has been a notable trend in the application of deep learning in graph clustering. However, it is worth noting that existing deep graph clustering methods primarily focus on the topological information of nodes while overlooking the use of attribute information in the learned feature representations. In addition, they do not address the consistency of the space distribution in attribute and structure clustering results. To tackle these critical issues, a novel structured deep graph clustering network with consistency constraint (CC-DGC) is proposed. The network first constructs an autoencoder to learn and transmit hierarchical attribute information to the graph autoencoder (GAE). Subsequently, the GAE integrates the received hierarchical attribute information with extracted topological information to generate enhanced clustering representations. Moreover, this paper designs a consistency constraint module to promote consistency between the autoencoder and the GAE by optimizing the cluster space distributions they produce. Finally, the feature extraction and clustering classification processes are synchronized and optimized in a self-supervised manner within a unified framework. Extensive experiments illustrate that the proposed CC-DGC demonstrates superiority over the state-of-the-art deep graph clustering methods on five benchmark datasets. [ABSTRACT FROM AUTHOR]

Attributed graph clustering or community detection which learns to cluster the nodes of a graph is a challenging task in graph analysis. Recently contrastive learning has shown significant results in various unsupervised graph learning tasks. In spite of the success of graph contrastive learning methods in self-supervised graph learning, using them for graph clustering is not well explored. In this paper, we introduce a contrastive learning framework for learning clustering-friendly node embedding. We propose Gaussian mixture information maximization which utilizes a mutual information maximization approach for node embedding. Meanwhile, in order to have a clustering-friendly embedding space, it imposes a mixture of Gaussians distribution on this space. The parameters of the contrastive node embedding model and the mixture distribution are optimized jointly in a unified framework. Experiments show that our clustering-directed embedding space can enhance clustering performance in comparison with the case where community structure of the graph is ignored during node representation learning. The results on real-world datasets demonstrate the effectiveness of our method in community detection. [ABSTRACT FROM AUTHOR]

In the Transformer architecture, positional encoding is a vital component because it provides the model with information about the structure and position of data. In Graph Transformer, there have been attempts to introduce different positional encodings and inject additional structural information. Therefore, in terms of integrating positional and structural information, we propose a Structural and Positional Ensembled Graph Transformer (SPEGT). We developed SPEGT by noting the different properties of structural and positional encodings of graphs and the similarity of their computational processes. We have set a unified component that integrates the functionalities: (i) Random Walk Positional Encoding, (ii) Shortest Path Distance between each node, and (iii) Hierarchical Cluster Encoding. We find a problem with a well-known positional encoding and experimentally verify that combining it with other encodings can solve their problem. In addition, SPEGT outperforms previous models on a variety of graph datasets. We also show that SPEGT using unified positional encoding, performs well on structurally indistinguishable graph data through error case analysis. [Display omitted] • We combined information of graph structures to create a novel positional encoding. • The components of the new unified encoding compensate for each other's shortcomings. • Our new architecture continuously injects unified information into the attention. • Our model performs better when edge information is scarce. • The model discriminates graphs that are structurally indistinguishable. [ABSTRACT FROM AUTHOR]

We present PyGenStability, a general-use Python software package that provides a suite of analysis and visualization tools for unsupervised multiscale community detection in graphs. PyGenStability finds optimized partitions of a graph at different levels of resolution by maximizing the generalized Markov Stability quality function with the Louvain or Leiden algorithm. The package includes automatic detection of robust graph partitions and allows the flexibility to choose quality functions for weighted undirected, directed, and signed graphs and to include other user-defined quality functions. [ABSTRACT FROM AUTHOR]

Graph clustering, an essential unsupervised learning task in data mining, has garnered significant attention in recent years. With the advent of deep learning, considerable progress has been made in this field. However, existing methods present several limitations: (1) Most encoder models employ Graph Convolutional Networks (GCNs) as encoders. However, GCNs assign equal weight to each neighboring node and have been shown to be oversmoothing, thereby impacting clustering performance. (2) Most algorithms do not fully utilize the original graph content and structural information, leading to incomplete embedding features. (3) These methods do not account for the specific distribution of clustering of embedding features and the enhancement of staged pseudo-labels on clustering tasks.In this study,we propose a novel end-to-end graph clustering model that leverages graph attention encoders. Specifically, we initially employ a graph attention encoder to extract the inherent information from the original graph. This process assigns varying weights to different nodes, thereby avoiding excessive smoothing. We also fully utilize the guidance of periodic pseudo-labels to facilitate the learning of potential features that are beneficial for clustering. In addition, to improve the model’s clustering performance, we introduce a regularization term that distributes the node features of different classifications across distinct low-dimensional spaces. Furthermore, to prevent the embedding features from straying from the original graph features, we design an information consistency module. Experimental results on the node graph datasets show that our model outperforms other state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Three‐dimensional (3D) structure information, now available at the proteome scale, may facilitate the detection of remote evolutionary relationships in protein superfamilies. Here, we illustrate this with the identification of a novel family of protein domains related to the ferredoxin‐like superfold, by combining (i) transitive sequence similarity searches, (ii) clustering approaches, and (iii) the use of AlphaFold2 3D structure models. Domains of this family were initially identified in relation with the intracellular biomineralization of calcium carbonates by Cyanobacteria. They are part of the large heavy‐metal‐associated (HMA) superfamily, departing from the latter by specific sequence and structural features. In particular, most of them share conserved basic amino acids (hence their name CoBaHMA for Conserved Basic residues HMA), forming a positively charged surface, which is likely to interact with anionic partners. CoBaHMA domains are found in diverse modular organizations in bacteria, existing in the form of monodomain proteins or as part of larger proteins, some of which are membrane proteins involved in transport or lipid metabolism. This suggests that the CoBaHMA domains may exert a regulatory function, involving interactions with anionic lipids. This hypothesis might have a particular resonance in the context of the compartmentalization observed for cyanobacterial intracellular calcium carbonates. [ABSTRACT FROM AUTHOR]

Graph clustering aims to divide nodes into different clusters without labels and has attracted great attention due to the success of graph neural networks (GNNs). Traditional GNN-based clustering methods are based on the homophilic assumption, i.e., connected nodes belong to the same clusters. However, this assumption is not always true, as heterophilic graphs are also ubiquitous in the real world, which limits the application of GNNs. Furthermore, these methods overlook global positions, which can result in erroneous clustering. To solve the aforementioned problems, we propose a novel model called Preserving Global Information for Graph Clustering with Masked Autoencoders (GCMA). We first propose a low–high-pass filter to capture meaningful low- and high-frequency information. Then, we propose a graph diffusion method to obtain the global position. Specifically, a parameterized Laplacian matrix is proposed to better control the global direction. To further enhance the learning ability of the autoencoders, we design a model with a masking strategy that enhances the learning ability. Extensive experiments on both homophilic and heterophilic graphs demonstrate GCMA's advantages over state-of-the-art baselines. [ABSTRACT FROM AUTHOR]

In recent years, multi-view graph clustering algorithms based on representations learning have received extensive attention. However, existing algorithms are still limited in two main aspects, first, most algorithms employ graph convolution networks to learn the local representations, but the presence of high-frequency noise in these representations limits the clustering performance. Second, in the process of constructing a global representation based on the local representations, most algorithms focus on the consistency of each view while ignoring complementarity, resulting in lower representation quality. To address the aforementioned issues, a local-global representation enhancement for multi-view graph clustering algorithm is proposed in this paper. First, the low-frequency signals in the local representations are enhanced by a low-pass graph encoder, which yields smoother and more suitable local representations for clustering. Second, by introducing an attention mechanism, the local embedded representations of each view can be weighted and fused to obtain a global representation. Finally, to enhance the quality of the global representation, it is jointly optimized using the neighborhood contrastive loss and reconstruction loss. The final clustering results are obtained by applying the k-means algorithm to the global representation. A wealth of experiments have validated the effectiveness and robustness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Graph clustering has been a hot research topic and is widely used in many fields, such as community detection in social networks. Lots of works combining auto-encoder and graph neural networks have been applied to clustering tasks by utilizing node attributes and graph structure. These works usually assumed the inherent parameters (i.e., size and variance) of different clusters in the latent embedding space are homogeneous, and hence the assigned probability is monotonous over the Euclidean distance between node embeddings and centroids. Unfortunately, this assumption usually does not hold since the size and concentration of different clusters can be quite different, which limits the clustering accuracy. In addition, the node embeddings in deep graph clustering methods are usually L2 normalized so that it lies on the surface of a unit hyper-sphere. To solve this problem, we proposed Deep Adaptive Graph Clustering via von Mises-Fisher distributions, namely DAGC. DAGC assumes the node embeddings H can be drawn from a von Mises-Fisher distribution and each cluster k is associated with cluster inherent parameters ρk which includes cluster center μ and cluster cohesion degree κ. Then we adopt an EM-like approach (i.e., (H|ρ) and (ρ|H), respectively) to learn the embedding and cluster inherent parameters alternately. Specifically, with the node embeddings, we proposed to update the cluster centers in an attraction-repulsion manner to make the cluster centers more separable. And given the cluster inherent parameters, a likelihood-based loss is proposed to make node embeddings more concentrated around cluster centers. Thus, DAGC can simultaneously improve the intra-cluster compactness and inter-cluster heterogeneity. Finally, extensive experiments conducted on four benchmark datasets have demonstrated that the proposed DAGC consistently outperforms the state-of-the-art methods, especially on imbalanced datasets. [ABSTRACT FROM AUTHOR]

This paper extensively reviews the literature of community detection in complex networks and proposes a general classification describing the main models used for this purpose. Besides, a statistical study of the distribution of the recent relevant literature has been realized to picture the tendency of the models used by the main works published in the context of community detection. This mainly helped the understanding of the suitable community model to be used in each real-world network application. Furthermore, we establish a critical study of the state-of-the-art approaches according to the proposed classification. Moreover, we investigate the relevant applications of communities in networks and we establish a statistical study to illustrate the distribution of research works in the field of community detection. Finally, we discuss several open issues and future research directions of approaches and applications that would be worth investigating in the area of community detection. [ABSTRACT FROM AUTHOR]

Deep graph clustering is an unsupervised learning task that divides nodes in a graph into disjoint regions with the help of graph auto-encoders. Currently, such methods have several problems, as follows. (1) The deep graph clustering method does not effectively utilize the generated pseudo-labels, resulting in sub-optimal model training results. (2) Each cluster has a different confidence level, which affects the reliability of the pseudo-label. To address these problems, we propose a Deep Self-supervised Attribute Graph Clustering model (DSAGC) to fully leverage the information of the data itself. We divide the proposed model into two parts: an upstream model and a downstream model. In the upstream model, we use the pseudo-label information generated by spectral clustering to form a new high-confidence distribution with which to optimize the model for a higher performance. We also propose a new reliable sample selection mechanism to obtain more reliable samples for downstream tasks. In the downstream model, we only use the reliable samples and the pseudo-label for the semi-supervised classification task without the true label. We compare the proposed method with 17 related methods on four publicly available citation network datasets, and the proposed method generally outperforms most existing methods in three performance metrics. By conducting a large number of ablative experiments, we validate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Graph clustering is a fundamental technique in data analysis with applications in many different fields. While there is a large body of work on clustering undirected graphs, the problem of clustering directed graphs is much less understood. The analysis is more complex in the directed graph case for two reasons: the clustering must preserve directional information in the relationships between clusters, and directed graphs have non-Hermitian adjacency matrices whose properties are less conducive to traditional spectral methods. Here, we consider the problem of partitioning the vertex set of a directed graph into k ≥ 2 clusters so that edges between different clusters tend to follow the same direction. We present an iterative algorithm based on spectral methods applied to new Hermitian representations of directed graphs. Our algorithm performs favourably against the state-of-the-art, both on synthetic and real-world data sets. Additionally, it can identify a 'meta-graph' of k vertices that represents the higher-order relations between clusters in a directed graph. We showcase this capability on data sets about food webs, biological neural networks, and the online card game Hearthstone. [ABSTRACT FROM AUTHOR]

This paper addresses the issue of reliable and automated analog circuit’s structure recognition (ACSR). First, it presents a comprehensive critical review of the related state-of-the-art. Then, essentially, this study proposes and validates a novel approach for realizing a dependable structure recognition system for analog circuits through a comprehensive ontology definition, some transformation tools, scene modeling through graph models, and then, by involving a graph attention neural network (GAT) model. Knowingly, identifying sub-circuits requires, in the brute-force mode, extensive screening of the numerous alternative substructures that can be constructed from the basic elements (i.e. the transistors) in presence, especially w.r.t. the actual connectivity topology amongst them; this is evidently a very complex and challenging endeavor. The relevant state-of-the-art has involved mostly unsupervised learning approaches to tackle this analog circuit’s structure recognition-related challenging task, whereby they have reached a clear limitation of not (or only very hardly) reaching beyond 90% to 93% accuracy/precision. But in this work, we develop, for the first time, a comprehensive supervised-learning approach that demonstrates its clear superiority by enabling the reaching of a recognition accuracy or precision that is reliably in the range beyond 99% (or even 100%) for each subblock of the analog circuit. The supervised clustering approach developed and validated in this study consists of a comprehensive modeling and conceptual pipeline that is implemented around and through a Graph Attention Neural Network model, which ensures a reliable recognition of sub-blocks of analog circuits and their related internal adjacency connectivity topology. Besides the modeling pipeline, this study also develops a set of tools for mapping an analog circuit’s schematics into a graph model. To overcome the limited and unbalanced samples for training the graph neural model, this study proposes a special novel augmentation strategy based on a graph sub-cropping technique. This augmentation technique is embedded in a smart stepwise augmentation protocol that leads at the end, through iterative additional dedicated training steps to a significant progressive increase of the recognition accuracy by the graph neural model until reaching more than 99%, better 100%, for each of the subblocks of the analog circuits as demonstrated in the demonstration case-study presented. Indeed, this paper’s quintessence represents a significant breakthrough in view of the clear outperforming of the currently relevant related state-of-the-art.

In this article, a novel infrared maritime small target detection method, called local dissimilarity measure with anti-interference based on global graph clustering (LDMGGC), is proposed. The Wasserstein distance is introduced to calculate the dissimilarity of gray level distribution between a central region and its neighborhoods. These dissimilarities construct the feature of a region. With this feature, detection for recalling all suspected targets is achieved. As the maritime interferences among suspected targets are able to be clustered, relaxing mutual k nearest neighbor graph is introduced in global graph clustering for filtering interferences. With this method, real targets are detected and maritime interferences are filtered out. Experiments are conducted on three maritime datasets and a nonmaritime dataset for comparison. On three datasets, the proposed method achieves the best Receiver Operating Characteristic curves and Area Under Curve (0.99529, 0.99945, 0.99573, and 0.9906) values, meaning that the proposed method has high detection probability and low false-alarm ratio. Target Hit Rate (98.04%, 97.96%, 100%, and 99.24%) and Intersection of Union (0.8170, 0.7542, 0.5824, 0.7707) on four datasets of the proposed method show it has a strong ability to suppress the interferences.

In order to help learners identify suitable learning resources and sequences sets for personalized learning from a large number of online learning resources, a label propagation algorithm on directed edge weights (LPADEW) was proposed for clustering micro-learning units and sequence that belong to the same learning period for specific learners. Two improvements to the label propagation algorithm were made: the label update order was determined according to the utilization rate of the unit node, the randomness of node update order was reduced. The accumulated value of the directed edge weights of the pre-neighbor and the postneighbor of the current element node was used to update the label, and the label weight was used in the label updating strategy, which can not only reduce the randomness of label updating, but also avoids the formation of giant cluster. Experimental result shows that LPADEW algorithm performs well on real datasets of micro-learning and synthetic datasets. [ABSTRACT FROM AUTHOR]

The multi-layer network consists of the interactions between different layers, where each layer of the network is depicted as a graph, providing a comprehensive way to model the underlying complex systems. The layer-specific modules of multi-layer networks are critical to understanding the structure and function of the system. However, existing methods fail to characterize and balance the connectivity and specificity of layer-specific modules in networks because of the complicated inter- and intra-coupling of various layers. To address the above issues, a joint learning graph clustering algorithm (DRDF) for detecting layer-specific modules in multi-layer networks is proposed, which simultaneously learns the deep representation and discriminative features. Specifically, DRDF learns the deep representation with deep nonnegative matrix factorization, where the high-order topology of the multi-layer network is gradually and precisely characterized. Moreover, it addresses the specificity of modules with discriminative feature learning, where the intra-class compactness and inter-class separation of pseudo-labels of clusters are explored as self-supervised information, thereby providing a more accurate method to explicitly model the specificity of the multi-layer network. Finally, DRDF balances the connectivity and specificity of layer-specific modules with joint learning, where the overall objective of the graph clustering algorithm and optimization rules are derived. The experiments on ten multi-layer networks showed that DRDF not only outperforms eight baselines on graph clustering but also enhances the robustness of algorithms. [ABSTRACT FROM AUTHOR]

The identification of events from social media platforms such as Twitter (now known as X) is a hot research problem. It has applications in diverse domains such as journalism, marketing, public safety, crisis management and disaster response. The process includes the identification, monitoring, and analysis of events or incidents while they are being discussed or reported on Twitter. When it comes to identifying events from tweets (i.e. feeds from Twitter), many of the currently available event detection methods mainly rely on keyword burstiness features or structural changes in the network. However, due to the intricate characteristics of tweets and the ever-changing nature of events, they frequently fail to recognise noteworthy occurrences before they become trending. Moreover, these methods face difficulties when it comes to capturing the evolving characteristics of events with limited or insufficient contextual information. In this paper, we propose a window-based tweet-processing method called EDTBERT for detecting events and tracking the evolution of events over time. Our proposed method utilizes the structural and semantic affinities that exist among words in tweets. The method starts by generating graph of tweets, where tweets are represented as nodes, and edges are the similarities between tweets. The method utilizes overlapping hashtags and named entities to capture the structural relationship between tweets. Additionally, a pre-trained sentence transformer model, specifically BERT, is employed to collect contextual knowledge and find semantically similar tweets. Next, the graph clustering technique is employed to identify optimized event clusters. Subsequently, our method generates chain of event clusters for each event to track the evolving variation of the event over time by utilising the "Maximum-Weight Bipartite Graph Matching" (MWBGM) algorithm. The effectiveness of our approach is assessed using standard Tweet Datasets. Our evaluation demonstrates that our approach outperforms the baseline approaches. [ABSTRACT FROM AUTHOR]

The joint use of node features and network topology to detect communities is called community detection in attributed networks. Most of the existing work along this line has been carried out through objective function optimization and has proposed numerous approaches. However, they tend to focus only on lower-order details, i.e., capture node features and network topology from node and edge views, and purely seek a higher degree of optimization to guarantee the quality of the found communities, which exacerbates unbalanced communities and free-rider effect. To further clarify and reveal the intrinsic nature of networks, we conduct triangle-oriented community detection considering node features and network topology. Specifically, we first introduce a triangle-based quality metric to preserve higher-order details of node features and network topology, and then formulate so-called two-level constraints to encode lower-order details of node features and network topology. Finally, we develop a local search framework based on optimizing our objective function consisting of the proposed quality metric and two-level constraints to achieve both non-overlapping and overlapping community detection in attributed networks. Extensive experiments demonstrate the effectiveness and efficiency of our framework and its potential in alleviating unbalanced communities and free-rider effect. [ABSTRACT FROM AUTHOR]

The paper tackles the problem of clustering multiple networks, directed or not, that do not share the same set of vertices, into groups of networks with similar topology. A statistical model-based approach based on a finite mixture of stochastic block models is proposed. A clustering is obtained by maximizing the integrated classification likelihood criterion. This is done by a hierarchical agglomerative algorithm, that starts from singleton clusters and successively merges clusters of networks. As such, a sequence of nested clusterings is computed that can be represented by a dendrogram providing valuable insights on the collection of networks. Using a Bayesian framework, model selection is performed in an automated way since the algorithm stops when the best number of clusters is attained. The algorithm is computationally efficient, when carefully implemented. The aggregation of clusters requires a means to overcome the label-switching problem of the stochastic block model and to match the block labels of the networks. To address this problem, a new tool is proposed based on a comparison of the graphons of the associated stochastic block models. The clustering approach is assessed on synthetic data. An application to a set of ecological networks illustrates the interpretability of the obtained results. [ABSTRACT FROM AUTHOR]

Scene-based recommendation has proven its usefulness in E-commerce, by recommending commodities based on a given scene. However, scenes are typically unknown in advance, which necessitates scene discovery for E-commerce. In this article, we study scene discovery for E-commerce systems. We first formalize a scene as a set of commodity categories that occur simultaneously and frequently in real-world situations, and model an E-commerce platform as a heterogeneous information network (HIN), whose nodes and links represent different types of objects and different types of relationships between objects, respectively. We then formulate the scene mining problem for E-commerce as an unsupervised learning problem that finds the overlapping clusters of commodity categories in the HIN. To solve the problem, we propose a non-negative matrix factorization based method SMEC (Scene Mining for E-Commerce), and theoretically prove its convergence. Using six real-world E-commerce datasets, we finally conduct an extensive experimental study to evaluate SMEC against 13 other methods, and show that SMEC consistently outperforms its competitors with regard to various evaluation measures. [ABSTRACT FROM AUTHOR]

Graph clustering is the process of labeling nodes so that nodes sharing common labels form densely connected subgraphs with sparser connections to the remaining vertices. Because of its difficult formulation, we translate the intra-cluster density maximization problem to a distance minimization problem. To achieve this reformulation, we use a novel vertex–vertex distance that accurately reflects density. Specifically, we extend the recent binary quadratic K -medoids formulation to graph clustering. We also generalize a quadratic formulation originally designed for partitioning complete graphs. Because binary quadratic optimization is an NP-hard problem, we obtain numerical solutions for these formulations through the use of two novel Boltzmann machine (meta-)heuristics. For benchmarking purposes, we compare solution quality and computational performances to those obtained using a commercial solver, Gurobi. We also compare clustering quality to the clusters obtained using the popular Louvain modularity maximization method. Our initial results clearly demonstrate the superiority of our problem formulations combined with our Boltzmann machines. In the case of smaller less complex graphs, our formulations solved using Boltzmann machines provide the same solutions as Gurobi, but with solution times that are orders of magnitude lower. In the case of larger and more complex graphs, Gurobi either fails to return meaningful results within a reasonable time frame or returns inferior results. Finally, we also note that both our clustering formulations, the distance minimization and K -medoids, when solved using our Boltzmann machines, yield clusters of superior quality to those obtained with the Louvain algorithm. [ABSTRACT FROM AUTHOR]

As the size of graph data grows exponentially, it is usually processed by parallel and distributed computing environment. During parallel processing, the first step is to divide the graph data into many subgraphs and then place them on different computational nodes. However, the existing graph clustering methods cannot adapt to parallel processing or improve computing performance. The main reason is that these methods only focus on the graph data but do not care about the graph's application algorithm. Therefore, this paper addresses a graph clustering method that supports parallel processing by perceiving the application algorithm semantics. We specifically focus on the characteristic of "tight inside and loose outside". Based on this characteristic, we give a new formula for calculating the modularity of the subgraph. In a graph application, graph data and its associated application algorithm are not separated from each other. Thus, we also focus on the execution patterns of the application algorithm. Combining the modularity of a subgraph and execution patterns of an application algorithm, we present the critical concept of semantic serial degree as a new criterion for big graph clustering. Consequently, we propose a graph clustering method that effectively balances the importance between the graph data and its associated application algorithm. By achieving this balance, our approach ensures that the final clustering results are more suitable for parallel and distributed processing. Extended experiments show that our proposed graph clustering method is more general and compatible with traditional clustering methods. Compared with FastUnfolding, a state-of-the-art graph clustering method, the completion times of an application algorithm are significantly reduced due to the help of the proposed graph clustering method. [ABSTRACT FROM AUTHOR]

Graph clustering has received considerable attention recently, and its applications are numerous, ranging from the detection of social communities to the clustering of computer networks. It is classified as an NP-class problem, and several algorithms have been proposed with specific objectives. There also exist various quality metrics for evaluating them. Having clusters with the required density can be beneficial because it permits the effective deployment of resources. This study proposes an approach to partitioning and overlapping clustering of undirected unweighted graphs, allowing users to specify the required density of resultant clusters. This required density is achieved by means of 'Relative Density'. The proposed algorithm adopts an edge-based approach, commencing with the determination of the edge degree for each edge. The main clustering process is then initiated by an edge with an average degree. A cluster is expanded by considering adjacent edges that can be included while monitoring the relative density of the cluster. Eight empirical networks with diverse characteristics are used to validate the proposed algorithm for both partitioning and overlapping clustering. Their results are assessed using an appropriate metric known as the mean relative density deviation coefficient (MRDDC). This is the first work that attempts to carry out partitioning and overlapping graph clustering, which allows user-specified density. [ABSTRACT FROM AUTHOR]