Search

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.

Graph clustering has attracted many interests in recent years, with numerous applications ranging from the clustering of computer networks to the detection of social communities. It presents a challenging NP-class problem, and as a result, numerous algorithms have been developed, each tailored to specific objectives and quality metrics for evaluation. This research commences by categorizing existing graph clustering algorithms based on two distinct perspectives: parameter-free algorithms and user-defined or adjustable parametric algorithms. Quality metrics are further categorized into three distinct groups: internal connectivity, external connectivity, and a combination of both. If a task can be represented by a simple undirected and unweighted graph, from a management and deployment of resources perspective, having clusters of some kind of similar density is advantageous as it allows efficient management. This research introduces a partitioning graph clustering algorithm that allows users to specify the desired density of a cluster by means of ‘relative density’. Clustering process involves the determination of all triangles (i.e., smallest cliques) and selecting a clique as an initial cluster. The expansion of a cluster is done by adding adjacent cliques while the required relative density is monitored. Existing metrics are found unsuitable for evaluating the proposed method; therefore, a suitable new metric, the Mean Relative Density Deviation Coefficient (MRDDC), is introduced.

The structure of many complex networks includes edge directionality and weights on top of their topology. Network analysis that can seamlessly consider combination of these properties are desirable. In this paper, we study two important such network analysis techniques, namely, centrality and clustering. An information-flow based model is adopted for clustering, which itself builds upon an information theoretic measure for computing centrality. Our principal contributions include (1) a generalized model of Markov entropic centrality with the flexibility to tune the importance of node degrees, edge weights and directions, with a closed-form asymptotic analysis, which (2) leads to a novel two-stage graph clustering algorithm. The centrality analysis helps reason about the suitability of our approach to cluster a given graph, and determine ‘query’ nodes, around which to explore local community structures, leading to an agglomerative clustering mechanism. Our clustering algorithm naturally inherits the flexibility to accommodate edge directionality, as well as different interpretations and interplay between edge weights and node degrees. Extensive benchmarking experiments are provided, using both real-world networks with ground truth and synthetic networks.

Food recommender-systems are considered an effective tool to help users adjust their eating habits and achieve a healthier diet. This paper aims to develop a new hybrid food recommender-system to overcome the shortcomings of previous systems, such as ignoring food ingredients, time factor, cold start users, cold start food items and community aspects. The proposed method involves two phases: food content-based recommendation and user-based recommendation. Graph clustering is used in the first phase, and a deep-learning based approach is used in the second phase to cluster both users and food items. Besides a holistic-like approach is employed to account for time and user-community related issues in a way that improves the quality of the recommendation provided to the user. We compared our model with a set of state-of-the-art recommender-systems using five distinct performance metrics: Precision, Recall, F1, AUC and NDCG. Experiments using dataset extracted from “Allrecipes.com” demonstrated that the developed food recommender-system performed best.

Multinational corporations have multiple databases distributed throughout their branches, which store millions of transactions per day. For business applications, identifying disjoint clusters of similar and relevant databases contributes to learning the common buying patterns among customers and also increases the profits by targeting potential clients in the future. This process is called clustering, which is an important unsupervised technique for big data mining. In this article, we present an effective approach to search for the optimal clustering of multiple transaction databases in a weighted undirected similarity graph. To assess the clustering quality, we use dual gradient descent to minimize a constrained quasi-convex loss function whose parameters will determine the edges needed to form the optimal database clusters in the graph. Therefore, finding the global minimum is guaranteed in a finite and short time compared with the existing non-convex objectives where all possible candidate clusterings are generated to find the ideal clustering. Moreover, our algorithm does not require specifying the number of clusters a priori and uses a disjoint-set forest data structure to maintain and keep track of the clusters as they are updated. Through a series of experiments on public data samples and precomputed similarity matrices, we show that our algorithm is more accurate and faster in practice than the existing clustering algorithms for multi-database mining.

Advances in bio-technologies enable the generation of genomic data from various platforms. The accumulated omic data provides an opportunity to exploit the underlying mechanisms of cancers, and imposes a great challenge on designing algorithms for the integration of heterogeneous genomic data. Clustering of gene interaction networks is a promising approach for revealing the structure and functions of genes. However, current algorithms are criticized for either ignoring the attributes of genes or their high complexity. To overcome these problems, we propose a novel algorithm for cancer attributed networks (called jGENMF-AN), wherein graph representation and nonnegative matrix factorization are integrated. Specifically, graph representation learning is employed to obtain the low-dimensional features by preserving topology of the attributed networks, thereby reducing the complexity of the algorithm. To address heterogeneity of the topological features and attributes of genes, nonnegative matrix factorization for graph embedding and dimension reduction for the attribute matrix are jointly learned with a smoothness strategy. The experimental results indicate that jGENMF-AN is more accurate than state-of-the-art methods in the social and cancer attributed networks. The proposed model and algorithm provide an effective strategy for the integrative analysis of genomic data.

Although automatic fuzzy clustering framework (AFCF) based on improved density peak clustering is able to achieve automatic and efficient image segmentation, the framework suffers from two problems. The first one is that the adaptive morphological reconstruction (AMR) employed by the AFCF is easily influenced by the initial structuring element. The second one is that the improved density peak clustering using a density balance strategy is complex for finding potential clustering centers. To address these two problems, we propose a fast and automatic image segmentation algorithm using superpixel-based graph clustering (FAS-SGC). The proposed algorithm has two major contributions. First, the AMR based on regional minimum removal (AMR-RMR) is presented to improve the superpixel result generated by the AMR. The binary morphological reconstruction is performed on a regional minimum image, which overcomes the problem that the initial structuring element of the AMR is chosen empirically, since the geometrical information of images is effectively explored and utilized. Second, we use an eigenvalue gradient clustering (EGC) instead of improved density peak (DP) algorithms to obtain potential clustering centers, since the EGC is faster and requires fewer parameters than the DP algorithm. Experiments show that the proposed algorithm is able to achieve automatic image segmentation, providing better segmentation results while requiring less execution time than other state-of-the-art algorithms.

Identifying geochemical patterns from backgrounds and generating associated mineralization remains challenging due to the complex structure of mineral deposits. To learn how to identify geochemical anomalies that are spatially associated with mineralization, we need in-depth knowledge of the dependence process. Quantitative association rules (QARs) are applied to discover remarkable relations and dependencies between attributes in a dataset, but it is difficult to generate relationships from geochemical data. In previous studies, no methodology to find association rules is proposed to deal with geochemical data problem, and the classical methods designed for Boolean and nominal attributes require previous discretization, which makes the whole process limited in processing complex data. In this paper, we proposed a hybrid method of graph clustering and quantitative association rules (GCQAR) as a new way of identifying significant geochemical patterns. Graph Clustering (GC) is used as partitioning paradigm because of its ability to handle large-scale datasets. The GC is based on modularity to effectively generate the groups of the graph, to avoid the over-partitioning, and to cover all the rules. In each partition, a set of geochemical quantitative association rules is produced. The results obtained in the experimental study performed on data collected in the field of Xiaoshan, Henan province, China. Our GCQAR has significant benefits in terms of recognition geochemical patterns compared to the traditional methods used in the field of geochemistry.

Graph clustering is to partition a large graph into several subgraphs according to the topological structure and node characteristics of the graph. It can discover the community structures of complex networks and thus help researchers better understand the characteristics and structures of complex networks. This paper first proposes the concepts of direct attraction force and indirect attraction force. Then, it defines a new structural similarity, attraction-force similarity. Finally, the AF-Cluster algorithm is proposed based on the attraction-force similarity. Through the experimental analysis, we can conclude that the AF-Cluster algorithm is effective for clustering graph compared with other contrast algorithms.

As one of the most popular clustering techniques, graph clustering has attracted many researchers in the field of machine learning and data mining. Generally speaking, graph clustering partitions the data points into different categories according to their pairwise similarities. Therefore, the clustering performance is largely determined by the quality of the similarity graph. The similarity graph is usually constructed based on the data points' distances. However, the data structure may be corrupted by outliers. To deal with the outliers, we propose a capped l1 -norm sparse representation method (CSR) in this paper. The main contribution of this paper is threefold: 1) a similarity graph with clear cluster structure is learned by employing sparse representation with proper constraints; (2) the capped l1 -norm loss is utilized to remove the outliers, which ensures the graph quality; and 3) an iterative algorithm is developed to optimize the proposed non-convex problem. The extensive experiments on real-world datasets show the superiority of the proposed method over the state-of-the-art, and demonstrate its robustness to the outliers.

As the continuous development of mobile social networks, the structure of the mobile social network increasingly becomes complex. It not only speeds up information transmission between people but also expands the scope of information exchange, which has become an essential and important social media in people's social life. How to effectively identify and classify these online communities has important practical significance for the study of social networks. Correctly detecting the community structure of mobile social networks can not only improve the accuracy of friend recommendation, link prediction, service user positioning, product marketing, and other aspects but also provide an important basis for the monitoring of online public opinion. But the traditional social network cluster method based on the trust degree mainly calculates the user trust by analyzing the interactive feedback information between users. This method cannot effectively solve the “cold start” problem in the trust calculation process, that is, for the new network node, the trust value of this node cannot be accurately measured due to the lack of interaction with other nodes. Focusing on this problem, we propose a Gaussian pigeon-oriented graph clustering algorithm for social networks' cluster in this paper. A graph model is first built. Then, an efficient K-medoid algorithm is utilized to search the user center in all groups. The Gaussian pigeon algorithm is used to search the similarity between each user and the central user. Users that meet the similarity threshold are divided into the same user group. Finally, the simulation results show that the proposed method has better cluster effect than other state-of-the-art social networks' clustering approaches.

Many current analyses on protein-protein interaction (PPI) networks concentrate on developing the algorithms for identifying the functional modules within the PPI networks. However, understanding the internal structure in the functional modules is needed to define their roles within the entire network. We propose the use of a two-club meso-scale structure that possesses refined inner topological structural properties, useful for deciphering the aforementioned obscure structural supporting evidences. In this paper, we: 1) illustrate the feasibility and advantages of modeling functional modules as two-clubs in PPI networks by taking statistics on the diameter distribution of benchmark functional modules within several golden standard sets; 2) categorize the two-clubs into six subcategories through the use of well-defined internal graph-theoretic characterizations; and 3) analyze these six subcategories based on factors, such as their structure, and various metrics, such as topological centralities, the numbers of involved transcription factors and essential genes, and the numbers of matched protein complexes or GO terms. Our structure-driven analysis allows us to predict the roles of identified functional modules from their network structure alone. Our subcategories of coteries and social circles serve as a classification scheme for determining which functional modules are central, regional, and satellite and which are coordinating. Experimental results show that in order to precisely control and examine the PPI networks for further research, a clear understanding of how the internal topology of modules affects their function is essential.

Data mining task is a challenge on finding a high-quality community structure from largescale networks. The distance dynamics model was proved to be active on regular-size network community, but it is difficult to discover the community structure effectively from the large-scale network (0.1-1 billion edges), due to the limit of machine hardware and high time complexity. In this paper, we proposed a parallel community detection algorithm based on the distance dynamics model called P-Attractor, which is capable of handling the detection problem of large networks community. Our algorithm first developed a graph partitioning method to divide large network into lots of sub-networks, yet maintaining the complete neighbor structure of the original network. Then, the traditional distance dynamics model was improved by the dynamic interaction process to simulate the distance evolution of each sub-network. Finally, we discovered the real community structure by removing all external edges after evolution process. In our extensive experiments on multiple synthetic networks and real-world networks, the results showed the effectiveness and efficiency of P-Attractor, and the execution time on 4 threads and 32 threads are around 10 and 2 h, respectively. Our proposed algorithm is potential to discover community from a billion-scale network, such as Uk-2007.

Network communities, which are also known as network clusters, are typical latent structures in network data. Vertices in each of these communities tend to interact more and share similar features with each other. Community identification and feature summarization are significant tasks of network analytics. To perform either of the two tasks, there have been several approaches proposed, taking into the consideration of different categories of information carried by the network, e.g., edge structure, node attributes, or both aforementioned. But few of them are able to discover communities and summarize their features simultaneously. To address this challenge, we propose a novel latent factor model for community identification and summarization (LFCIS). To perform the task, the LFCIS first formulates an objective function that evaluating the overall clustering quality taking into the consideration of both edge topology and node features in the network. In the objective function, the LFCIS also adopts an effective component that ensures those vertices sharing with both similar local structures and features to be located into the same clusters. To identify the optimal cluster membership for each vertex, a convergent algorithm for updating the variables in the objective function is derived and used by LFCIS. The LFCIS has been tested with six sets of network data, including synthetic and real networks, and compared with several state-of-the-art approaches. The experimental results show that the LFCIS outperforms most of the prevalent approaches to community discovery in social networks, and the LFCIS is able to identify the latent features that may characterize those discovered communities.