Journal articles: 'Graph classification'

1

Liu, Xien, Xinxin You, Xiao Zhang, Ji Wu, and Ping Lv. "Tensor Graph Convolutional Networks for Text Classification." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 05 (April 3, 2020): 8409–16. http://dx.doi.org/10.1609/aaai.v34i05.6359.

Full text

Abstract:

Compared to sequential learning models, graph-based neural networks exhibit some excellent properties, such as ability capturing global information. In this paper, we investigate graph-based neural networks for text classification problem. A new framework TensorGCN (tensor graph convolutional networks), is presented for this task. A text graph tensor is firstly constructed to describe semantic, syntactic, and sequential contextual information. Then, two kinds of propagation learning perform on the text graph tensor. The first is intra-graph propagation used for aggregating information from neighborhood nodes in a single graph. The second is inter-graph propagation used for harmonizing heterogeneous information between graphs. Extensive experiments are conducted on benchmark datasets, and the results illustrate the effectiveness of our proposed framework. Our proposed TensorGCN presents an effective way to harmonize and integrate heterogeneous information from different kinds of graphs.

APA, Harvard, Vancouver, ISO, and other styles

2

RIESEN, KASPAR, and HORST BUNKE. "GRAPH CLASSIFICATION BASED ON VECTOR SPACE EMBEDDING." International Journal of Pattern Recognition and Artificial Intelligence 23, no. 06 (September 2009): 1053–81. http://dx.doi.org/10.1142/s021800140900748x.

Full text

Abstract:

Graphs provide us with a powerful and flexible representation formalism for pattern classification. Many classification algorithms have been proposed in the literature. However, the vast majority of these algorithms rely on vectorial data descriptions and cannot directly be applied to graphs. Recently, a growing interest in graph kernel methods can be observed. Graph kernels aim at bridging the gap between the high representational power and flexibility of graphs and the large amount of algorithms available for object representations in terms of feature vectors. In the present paper, we propose an approach transforming graphs into n-dimensional real vectors by means of prototype selection and graph edit distance computation. This approach allows one to build graph kernels in a straightforward way. It is not only applicable to graphs, but also to other kind of symbolic data in conjunction with any kind of dissimilarity measure. Thus it is characterized by a high degree of flexibility. With several experimental results, we prove the robustness and flexibility of our new method and show that our approach outperforms other graph classification methods on several graph data sets of diverse nature.

APA, Harvard, Vancouver, ISO, and other styles

3

Aref'ev, Roman D., John T. Baldwin, and Marco Mazzucco. "Classification of δ-invariant amalgamation classes." Journal of Symbolic Logic 64, no. 4 (December 1999): 1743–50. http://dx.doi.org/10.2307/2586809.

Full text

Abstract:

Hrushovski's generalization of the Fraisse construction has provided a rich source of examples in model theory, model theoretic algebra and random graph theory. The construction assigns to a dimension function δ and a class K of finite (finitely generated) models a countable ‘generic’ structure. We investigate here some of the simplest possible cases of this construction. The class K will be a class of finite graphs; the dimension, δ(A), of a finite graph A will be the cardinality of A minus the number of edges of A. Finally and significantly we restrict to classes which are δ-invariant. A class of finite graphs is δ-invariant if membership of a graph in the class is determined (as specified below) by the dimension and cardinality of the graph, and dimension and cardinality of all its subgraphs. Note that a generic graph constructed as in Hrushovski's example of a new strongly minimal set does not arise from a δ-invariant class.We show there are countably many δ-invariant (strong) amalgamation classes of finite graphs which are closed under subgraph and describe the countable generic models for these classes. This analysis provides ω-stable generic graphs with an array of saturation and model completeness properties which belies the similarity of their construction. In particular, we answer a question of Baizhanov (unpublished) and Baldwin [5] and show that this construction can yield an ω-stable generic which is not saturated. Further, we exhibit some ω-stable generic graphs that are not model complete.

APA, Harvard, Vancouver, ISO, and other styles

4

Gumbrell, Lee, and James McKee. "A classification of all 1-Salem graphs." LMS Journal of Computation and Mathematics 17, no. 1 (2014): 582–94. http://dx.doi.org/10.1112/s1461157014000060.

Full text

Abstract:

AbstractOne way to study certain classes of polynomials is by considering examples that are attached to combinatorial objects. Any graph $G$ has an associated reciprocal polynomial $R_{G}$, and with two particular classes of reciprocal polynomials in mind one can ask the questions: (a) when is $R_{G}$ a product of cyclotomic polynomials (giving the cyclotomic graphs)? (b) when does $R_{G}$ have the minimal polynomial of a Salem number as its only non-cyclotomic factor (the non-trivial Salem graphs)? Cyclotomic graphs were classified by Smith (Combinatorial structures and their applications, Proceedings of Calgary International Conference, Calgary, AB, 1969 (eds R. Guy, H. Hanani, H. Saver and J. Schönheim; Gordon and Breach, New York, 1970) 403–406); the maximal connected ones are known as Smith graphs. Salem graphs are ‘spectrally close’ to being cyclotomic, in that nearly all their eigenvalues are in the critical interval $[-2,2]$. On the other hand, Salem graphs do not need to be ‘combinatorially close’ to being cyclotomic: the largest cyclotomic induced subgraph might be comparatively tiny.We define an $m$-Salem graph to be a connected Salem graph $G$ for which $m$ is minimal such that there exists an induced cyclotomic subgraph of $G$ that has $m$ fewer vertices than $G$. The $1$-Salem subgraphs are both spectrally close and combinatorially close to being cyclotomic. Moreover, every Salem graph contains a $1$-Salem graph as an induced subgraph, so these $1$-Salem graphs provide some necessary substructure of all Salem graphs. The main result of this paper is a complete combinatorial description of all $1$-Salem graphs: in the non-bipartite case there are $25$ infinite families and $383$ sporadic examples.

APA, Harvard, Vancouver, ISO, and other styles

5

Bera, Abhijit, Mrinal Kanti Ghose, and Dibyendu Kumar Pal. "Graph Classification Using Back Propagation Learning Algorithms." International Journal of Systems and Software Security and Protection 11, no. 2 (July 2020): 1–12. http://dx.doi.org/10.4018/ijsssp.2020070101.

Full text

Abstract:

Due to the propagation of graph data, there has been a sharp focus on developing effective methods for classifying the graph object. As most of the proposed graph classification techniques though effective are constrained by high computational overhead, there is a consistent effort to improve upon the existing classification algorithms in terms of higher accuracy and less computational time. In this paper, an attempt has been made to classify graphs by extracting various features and selecting the important features using feature selection algorithms. Since all the extracted graph-based features need not be equally important, only the most important features are selected by using back propagation learning algorithm. The results of the proposed study of feature-based approach using back propagation learning algorithm lead to higher classification accuracy with faster computational time in comparison to other graph kernels. It also appears to be more effective for large unlabeled graphs.

APA, Harvard, Vancouver, ISO, and other styles

6

Schmidt, Miriam, Günther Palm, and Friedhelm Schwenker. "Spectral graph features for the classification of graphs and graph sequences." Computational Statistics 29, no. 1-2 (November 30, 2012): 65–80. http://dx.doi.org/10.1007/s00180-012-0381-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Zhang, Yingxue, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. "Bayesian Graph Convolutional Neural Networks for Semi-Supervised Classification." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 5829–36. http://dx.doi.org/10.1609/aaai.v33i01.33015829.

Full text

Abstract:

Recently, techniques for applying convolutional neural networks to graph-structured data have emerged. Graph convolutional neural networks (GCNNs) have been used to address node and graph classification and matrix completion. Although the performance has been impressive, the current implementations have limited capability to incorporate uncertainty in the graph structure. Almost all GCNNs process a graph as though it is a ground-truth depiction of the relationship between nodes, but often the graphs employed in applications are themselves derived from noisy data or modelling assumptions. Spurious edges may be included; other edges may be missing between nodes that have very strong relationships. In this paper we adopt a Bayesian approach, viewing the observed graph as a realization from a parametric family of random graphs. We then target inference of the joint posterior of the random graph parameters and the node (or graph) labels. We present the Bayesian GCNN framework and develop an iterative learning procedure for the case of assortative mixed-membership stochastic block models. We present the results of experiments that demonstrate that the Bayesian formulation can provide better performance when there are very few labels available during the training process.

APA, Harvard, Vancouver, ISO, and other styles

8

SCHENKER, ADAM, MARK LAST, HORST BUNKE, and ABRAHAM KANDEL. "CLASSIFICATION OF WEB DOCUMENTS USING GRAPH MATCHING." International Journal of Pattern Recognition and Artificial Intelligence 18, no. 03 (May 2004): 475–96. http://dx.doi.org/10.1142/s0218001404003241.

Full text

Abstract:

In this paper we describe a classification method that allows the use of graph-based representations of data instead of traditional vector-based representations. We compare the vector approach combined with the k-Nearest Neighbor (k-NN) algorithm to the graph-matching approach when classifying three different web document collections, using the leave-one-out approach for measuring classification accuracy. We also compare the performance of different graph distance measures as well as various document representations that utilize graphs. The results show the graph-based approach can outperform traditional vector-based methods in terms of accuracy, dimensionality and execution time.

APA, Harvard, Vancouver, ISO, and other styles

9

Eilers, Søren, Gunnar Restorff, Efren Ruiz, and Adam P. W. Sørensen. "Geometric Classification of Graph C*-algebras over Finite Graphs." Canadian Journal of Mathematics 70, no. 2 (April 1, 2018): 294–353. http://dx.doi.org/10.4153/cjm-2017-016-7.

Full text

Abstract:

AbstractWe address the classification problem for graph C*-algebras of finite graphs (finitely many edges and vertices), containing the class of Cuntz-Krieger algebras as a prominent special case. Contrasting earlier work, we do not assume that the graphs satisfy the standard condition (K), so that the graph C*-algebras may come with uncountably many ideals.We find that in this generality, stable isomorphism of graph C*-algebras does not coincide with the geometric notion of Cuntz move equivalence. However, adding a modest condition on the graphs, the two notions are proved to be mutually equivalent and equivalent to the C*-algebras having isomorphicK-theories. This proves in turn that under this condition, the graph C*-algebras are in fact classifiable byK-theory, providing, in particular, complete classification when the C* - algebras in question are either of real rank zero or type I/postliminal. The key ingredient in obtaining these results is a characterization of Cuntz move equivalence using the adjacency matrices of the graphs.Our results are applied to discuss the classification problem for the quantumlens spaces defined by Hong and Szymański, and to complete the classification of graph C*-algebras associated with all simple graphs with four vertices or less.

APA, Harvard, Vancouver, ISO, and other styles

10

Magelinski, Thomas, David Beskow, and Kathleen M. Carley. "Graph-Hist: Graph Classification from Latent Feature Histograms with Application to Bot Detection." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 5134–41. http://dx.doi.org/10.1609/aaai.v34i04.5956.

Full text

Abstract:

Neural networks are increasingly used for graph classification in a variety of contexts. Social media is a critical application area in this space, however the characteristics of social media graphs differ from those seen in most popular benchmark datasets. Social networks tend to be large and sparse, while benchmarks are small and dense. Classically, large and sparse networks are analyzed by studying the distribution of local properties. Inspired by this, we introduce Graph-Hist: an end-to-end architecture that extracts a graph's latent local features, bins nodes together along 1-D cross sections of the feature space, and classifies the graph based on this multi-channel histogram. We show that Graph-Hist improves state of the art performance on true social media benchmark datasets, while still performing well on other benchmarks. Finally, we demonstrate Graph-Hist's performance by conducting bot detection in social media. While sophisticated bot and cyborg accounts increasingly evade traditional detection methods, they leave artificial artifacts in their conversational graph that are detected through graph classification. We apply Graph-Hist to classify these conversational graphs. In the process, we confirm that social media graphs are different than most baselines and that Graph-Hist outperforms existing bot-detection models.

APA, Harvard, Vancouver, ISO, and other styles

11

Wang, Yunzhe, George Baciu, and Chenhui Li. "A Layout-Based Classification Method for Visualizing Time-Varying Graphs." ACM Transactions on Knowledge Discovery from Data 15, no. 4 (June 2021): 1–24. http://dx.doi.org/10.1145/3441301.

Full text

Abstract:

Connectivity analysis between the components of large evolving systems can reveal significant patterns of interaction. The systems can be simulated by topological graph structures. However, such analysis becomes challenging on large and complex graphs. Tasks such as comparing, searching, and summarizing structures, are difficult due to the enormous number of calculations required. For time-varying graphs, the temporal dimension even intensifies the difficulty. In this article, we propose to reduce the complexity of analysis by focusing on subgraphs that are induced by closely related entities. To summarize the diverse structures of subgraphs, we build a supervised layout-based classification model. The main premise is that the graph structures can induce a unique appearance of the layout. In contrast to traditional graph theory-based and contemporary neural network-based methods of graph classification, our approach generates low costs and there is no need to learn informative graph representations. Combined with temporally stable visualizations, we can also facilitate the understanding of sub-structures and the tracking of graph evolution. The method is evaluated on two real-world datasets. The results show that our system is highly effective in carrying out visual-based analytics of large graphs.

APA, Harvard, Vancouver, ISO, and other styles

12

Jiang, Qiangrong, and Jiajia Ma. "A novel graph kernel on chemical compound classification." Journal of Bioinformatics and Computational Biology 16, no. 06 (December 2018): 1850026. http://dx.doi.org/10.1142/s0219720018500269.

Full text

Abstract:

Considering the classification of compounds as a nonlinear problem, the use of kernel methods is a good choice. Graph kernels provide a nice framework combining machine learning methods with graph theory, whereas the essence of graph kernels is to compare the substructures of two graphs, how to extract the substructures is a question. In this paper, we propose a novel graph kernel based on matrix named the local block kernel, which can compare the similarity of partial substructures that contain any number of vertexes. The paper finally tests the efficacy of this novel graph kernel in comparison with a number of published mainstream methods and results with two datasets: NCI1 and NCI109 for the convenience of comparison.

APA, Harvard, Vancouver, ISO, and other styles

13

Zhang, Yi, Lulu Wang, and Liandong Wang. "A Comprehensive Evaluation of Graph Kernels for Unattributed Graphs." Entropy 20, no. 12 (December 18, 2018): 984. http://dx.doi.org/10.3390/e20120984.

Full text

Abstract:

Graph kernels are of vital importance in the field of graph comparison and classification. However, how to compare and evaluate graph kernels and how to choose an optimal kernel for a practical classification problem remain open problems. In this paper, a comprehensive evaluation framework of graph kernels is proposed for unattributed graph classification. According to the kernel design methods, the whole graph kernel family can be categorized in five different dimensions, and then several representative graph kernels are chosen from these categories to perform the evaluation. With plenty of real-world and synthetic datasets, kernels are compared by many criteria such as classification accuracy, F1 score, runtime cost, scalability and applicability. Finally, quantitative conclusions are discussed based on the analyses of the extensive experimental results. The main contribution of this paper is that a comprehensive evaluation framework of graph kernels is proposed, which is significant for graph-classification applications and the future kernel research.

APA, Harvard, Vancouver, ISO, and other styles

14

Madhawa, Kaushalya, and Tsuyoshi Murata. "Active Learning for Node Classification: An Evaluation." Entropy 22, no. 10 (October 16, 2020): 1164. http://dx.doi.org/10.3390/e22101164.

Full text

Abstract:

Current breakthroughs in the field of machine learning are fueled by the deployment of deep neural network models. Deep neural networks models are notorious for their dependence on large amounts of labeled data for training them. Active learning is being used as a solution to train classification models with less labeled instances by selecting only the most informative instances for labeling. This is especially important when the labeled data are scarce or the labeling process is expensive. In this paper, we study the application of active learning on attributed graphs. In this setting, the data instances are represented as nodes of an attributed graph. Graph neural networks achieve the current state-of-the-art classification performance on attributed graphs. The performance of graph neural networks relies on the careful tuning of their hyperparameters, usually performed using a validation set, an additional set of labeled instances. In label scarce problems, it is realistic to use all labeled instances for training the model. In this setting, we perform a fair comparison of the existing active learning algorithms proposed for graph neural networks as well as other data types such as images and text. With empirical results, we demonstrate that state-of-the-art active learning algorithms designed for other data types do not perform well on graph-structured data. We study the problem within the framework of the exploration-vs.-exploitation trade-off and propose a new count-based exploration term. With empirical evidence on multiple benchmark graphs, we highlight the importance of complementing uncertainty-based active learning models with an exploration term.

APA, Harvard, Vancouver, ISO, and other styles

15

Wang, Ying, Hongji Wang, Hui Jin, Xinrui Huang, and Xin Wang. "Exploring graph capsual network for graph classification." Information Sciences 581 (December 2021): 932–50. http://dx.doi.org/10.1016/j.ins.2021.10.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Qin, Jian, Li Liu, Hui Shen, and Dewen Hu. "Uniform Pooling for Graph Networks." Applied Sciences 10, no. 18 (September 10, 2020): 6287. http://dx.doi.org/10.3390/app10186287.

Full text

Abstract:

The graph convolution network has received a lot of attention because it extends the convolution to non-Euclidean domains. However, the graph pooling method is still less concerned, which can learn coarse graph embedding to facilitate graph classification. Previous pooling methods were based on assigning a score to each node and then pooling only the highest-scoring nodes, which might throw away whole neighbourhoods of nodes and therefore information. Here, we proposed a novel pooling method UGPool with a new point-of-view on selecting nodes. UGPool learns node scores based on node features and uniformly pools neighboring nodes instead of top nodes in the score-space, resulting in a uniformly coarsened graph. In multiple graph classification tasks, including the protein graphs, the biological graphs and the brain connectivity graphs, we demonstrated that UGPool outperforms other graph pooling methods while maintaining high efficiency. Moreover, we also show that UGPool can be integrated with multiple graph convolution networks to effectively improve performance compared to no pooling.

APA, Harvard, Vancouver, ISO, and other styles

17

GIBERT, JAUME, ERNEST VALVENY, and HORST BUNKE. "EMBEDDING OF GRAPHS WITH DISCRETE ATTRIBUTES VIA LABEL FREQUENCIES." International Journal of Pattern Recognition and Artificial Intelligence 27, no. 03 (May 2013): 1360002. http://dx.doi.org/10.1142/s0218001413600021.

Full text

Abstract:

Graph-based representations of patterns are very flexible and powerful, but they are not easily processed due to the lack of learning algorithms in the domain of graphs. Embedding a graph into a vector space solves this problem since graphs are turned into feature vectors and thus all the statistical learning machinery becomes available for graph input patterns. In this work we present a new way of embedding discrete attributed graphs into vector spaces using node and edge label frequencies. The methodology is experimentally tested on graph classification problems, using patterns of different nature, and it is shown to be competitive to state-of-the-art classification algorithms for graphs, while being computationally much more efficient.

APA, Harvard, Vancouver, ISO, and other styles

18

Zhao, Yifei, and Fengqin Yan. "Hyperspectral Image Classification Based on Sparse Superpixel Graph." Remote Sensing 13, no. 18 (September 9, 2021): 3592. http://dx.doi.org/10.3390/rs13183592.

Full text

Abstract:

Hyperspectral image (HSI) classification is one of the major problems in the field of remote sensing. Particularly, graph-based HSI classification is a promising topic and has received increasing attention in recent years. However, graphs with pixels as nodes generate large size graphs, thus increasing the computational burden. Moreover, satisfactory classification results are often not obtained without considering spatial information in constructing graph. To address these issues, this study proposes an efficient and effective semi-supervised spectral-spatial HSI classification method based on sparse superpixel graph (SSG). In the constructed sparse superpixels graph, each vertex represents a superpixel instead of a pixel, which greatly reduces the size of graph. Meanwhile, both spectral information and spatial structure are considered by using superpixel, local spatial connection and global spectral connection. To verify the effectiveness of the proposed method, three real hyperspectral images, Indian Pines, Pavia University and Salinas, are chosen to test the performance of our proposal. Experimental results show that the proposed method has good classification completion on the three benchmarks. Compared with several competitive superpixel-based HSI classification approaches, the method has the advantages of high classification accuracy (>97.85%) and rapid implementation (<10 s). This clearly favors the application of the proposed method in practice.

APA, Harvard, Vancouver, ISO, and other styles

19

Tavakkoli, Maryam, Arsham Borumand Saeid, and Nosratollah Shajareh Poursalavati. "Classification of posets using zero-divisor graphs." Mathematica Slovaca 68, no. 1 (February 23, 2018): 21–32. http://dx.doi.org/10.1515/ms-2017-0076.

Full text

Abstract:

Abstract Halaš and Jukl associated the zero-divisor graph G to a poset (X,≤) with zero by declaring two distinct elements x and y of X to be adjacent if and only if there is no non-zero lower bound for {x, y}. We characterize all the graphs that can be realized as the zero-divisor graph of a poset. Using this, we classify posets whose zero-divisor graphs are the same. In particular we show that if V is an n-element set, then there exist $\begin{array}{} \sum\limits_{\log_2(n+1)\leq k\leq n}^{}\binom{n}{k}\binom{2^k-k-1}{n-k} \end{array} $ reduced zero-divisor graphs whose vertex sets are V.

APA, Harvard, Vancouver, ISO, and other styles

20

Perepelitsa, V. A., I. V. Kozin, and S. V. Kurapov. "Methods of classification and algorithms of graph coloring." Researches in Mathematics 16 (February 7, 2021): 135. http://dx.doi.org/10.15421/240816.

Full text

Abstract:

We study the connection between classifications on finite set and the problem of graph coloring. We consider the optimality criterion for classification of special type: h-classifications, which are built on the base of proximity measure. It is shown that the problem of finding the optimal h-classification can be reduced to the problem of coloring of non-adjacency graph vertices by the smallest possible number of colors. We consider algorithms of proper coloring of graph vertices.

APA, Harvard, Vancouver, ISO, and other styles

21

Sevugapandi, N., and C. P. Chandran. "Classification Algorithm for Gene Expression Graph and Manhattan Distance." Indonesian Journal of Electrical Engineering and Computer Science 5, no. 2 (February 1, 2017): 472. http://dx.doi.org/10.11591/ijeecs.v5.i2.pp472-478.

Full text

Abstract:

This proposed method focus on these issues by developing a novel classification algorithm by combining Gene Expression Graph (GEG) with Manhattan distance. This method will be used to express the gene expression data. Gene Expression Graph provides the optimal view about the relationship between normal and unhealthy genes. The method of using a graph-based gene expression to express gene information was first offered by the authors in [1] and [2], It will permits to construct a classifier based on an association between graphs represented for well-known classes and graphs represented for samples to evaluate. Additionally Euclidean distance is used to measure the strength of relationship which exists between the genes.

APA, Harvard, Vancouver, ISO, and other styles

22

Pogorelov, Boris A., and Marina A. Pudovkina. "Classification of distance-transitive orbital graphs of overgroups of the Jevons group." Discrete Mathematics and Applications 30, no. 1 (February 25, 2020): 7–22. http://dx.doi.org/10.1515/dma-2020-0002.

Full text

Abstract:

AbstractThe Jevons group AS̃n is an isometry group of the Hamming metric on the n-dimensional vector space Vn over GF(2). It is generated by the group of all permutation (n × n)-matrices over GF(2) and the translation group on Vn. Earlier the authors of the present paper classified the submetrics of the Hamming metric on Vn for n ⩾ 4, and all overgroups of AS̃n which are isometry groups of these overmetrics. In turn, each overgroup of AS̃n is known to define orbital graphs whose “natural” metrics are submetrics of the Hamming metric. The authors also described all distance-transitive orbital graphs of overgroups of the Jevons group AS̃n. In the present paper we classify the distance-transitive orbital graphs of overgroups of the Jevons group. In particular, we show that some distance-transitive orbital graphs are isomorphic to the following classes: the complete graph 2n, the complete bipartite graph K2n−1,2n−1, the halved (n + 1)-cube, the folded (n + 1)-cube, the graphs of alternating forms, the Taylor graph, the Hadamard graph, and incidence graphs of square designs.

APA, Harvard, Vancouver, ISO, and other styles

23

Peng, Hao, Jianxin Li, Qiran Gong, Yuanxin Ning, Senzhang Wang, and Lifang He. "Motif-Matching Based Subgraph-Level Attentional Convolutional Network for Graph Classification." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 5387–94. http://dx.doi.org/10.1609/aaai.v34i04.5987.

Full text

Abstract:

Graph classification is critically important to many real-world applications that are associated with graph data such as chemical drug analysis and social network mining. Traditional methods usually require feature engineering to extract the graph features that can help discriminate the graphs of different classes. Although recently deep learning based graph embedding approaches are proposed to automatically learn graph features, they mostly use a few vertex arrangements extracted from the graph for feature learning, which may lose some structural information. In this work, we present a novel motif-based attentional graph convolution neural network for graph classification, which can learn more discriminative and richer graph features. Specifically, a motif-matching guided subgraph normalization method is developed to better preserve the spatial information. A novel subgraph-level self-attention network is also proposed to capture the different impacts or weights of different subgraphs. Experimental results on both bioinformatics and social network datasets show that the proposed models significantly improve graph classification performance over both traditional graph kernel methods and recent deep learning approaches.

APA, Harvard, Vancouver, ISO, and other styles

24

Hughes, Lloyd, Simon Streicher, Ekaterina Chuprikova, and Johan Du Preez. "A Cluster Graph Approach to Land Cover Classification Boosting." Data 4, no. 1 (January 10, 2019): 10. http://dx.doi.org/10.3390/data4010010.

Full text

Abstract:

When it comes to land cover classification, the process of deriving the land classes is complex due to possible errors in algorithms, spatio-temporal heterogeneity of the Earth observation data, variation in availability and quality of reference data, or a combination of these. This article proposes a probabilistic graphical model approach, in the form of a cluster graph, to boost geospatial classifications and produce a more accurate and robust classification and uncertainty product. Cluster graphs can be characterized as a means of reasoning about geospatial data such as land cover classifications by considering the effects of spatial distribution, and inter-class dependencies in a computationally efficient manner. To assess the capabilities of our proposed cluster graph boosting approach, we apply it to the field of land cover classification. We make use of existing land cover products (GlobeLand30, CORINE Land Cover) along with data from Volunteered Geographic Information (VGI), namely OpenStreetMap (OSM), to generate a boosted land cover classification and the respective uncertainty estimates. Our approach combines qualitative and quantitative components through the application of our probabilistic graphical model and subjective expert judgments. Evaluating our approach on a test region in Garmisch-Partenkirchen, Germany, our approach was able to boost the overall land cover classification accuracy by 1.4% when compared to an independent reference land cover dataset. Our approach was shown to be robust and was able to produce a diverse, feasible and spatially consistent land cover classification in areas of incomplete and conflicting evidence. On an independent validation scene, we demonstrated that our cluster graph boosting approach was generalizable even when initialized with poor prior assumptions.

APA, Harvard, Vancouver, ISO, and other styles

25

Makarov, Ilya, Dmitrii Kiselev, Nikita Nikitinsky, and Lovro Subelj. "Survey on graph embeddings and their applications to machine learning problems on graphs." PeerJ Computer Science 7 (February 4, 2021): e357. http://dx.doi.org/10.7717/peerj-cs.357.

Full text

Abstract:

Dealing with relational data always required significant computational resources, domain expertise and task-dependent feature engineering to incorporate structural information into a predictive model. Nowadays, a family of automated graph feature engineering techniques has been proposed in different streams of literature. So-called graph embeddings provide a powerful tool to construct vectorized feature spaces for graphs and their components, such as nodes, edges and subgraphs under preserving inner graph properties. Using the constructed feature spaces, many machine learning problems on graphs can be solved via standard frameworks suitable for vectorized feature representation. Our survey aims to describe the core concepts of graph embeddings and provide several taxonomies for their description. First, we start with the methodological approach and extract three types of graph embedding models based on matrix factorization, random-walks and deep learning approaches. Next, we describe how different types of networks impact the ability of models to incorporate structural and attributed data into a unified embedding. Going further, we perform a thorough evaluation of graph embedding applications to machine learning problems on graphs, among which are node classification, link prediction, clustering, visualization, compression, and a family of the whole graph embedding algorithms suitable for graph classification, similarity and alignment problems. Finally, we overview the existing applications of graph embeddings to computer science domains, formulate open problems and provide experiment results, explaining how different networks properties result in graph embeddings quality in the four classic machine learning problems on graphs, such as node classification, link prediction, clustering and graph visualization. As a result, our survey covers a new rapidly growing field of network feature engineering, presents an in-depth analysis of models based on network types, and overviews a wide range of applications to machine learning problems on graphs.

APA, Harvard, Vancouver, ISO, and other styles

26

Iordanskii, M. A. "A Constructive Classification of Graphs." Modeling and Analysis of Information Systems 19, no. 4 (February 28, 2015): 144–53. http://dx.doi.org/10.18255/1818-1015-2012-4-144-153.

Full text

Abstract:

The classes of graphs closed regarding the set-theoretical operations of union and intersection are considered. Some constructive descriptions of the closed graph classes are set by the element and operational generating basses. Such bases have been constructed for many classes of graphs. The backward problems (when the generating bases are given and it is necessary to define the characteristic properties of corresponding graphs) are solved in the paper. Subsets of element and operational bases of the closed class of all graphs are considered as generating bases.

APA, Harvard, Vancouver, ISO, and other styles

27

Cho, Ilwoo, and Palle Jorgensen. "An Index for Graphs and Graph Groupoids." Axioms 11, no. 2 (January 25, 2022): 47. http://dx.doi.org/10.3390/axioms11020047.

Full text

Abstract:

In this paper, we consider certain quantities that arise in the images of the so-called graph-tree indexes of graph groupoids. In text, the graph groupoids are induced by connected finite-directed graphs with more than one vertex. If a graph groupoid GG contains at least one loop-reduced finite path, then the order of G is infinity; hence, the canonical groupoid index G:K of the inclusion K⊆G is either ∞ or 1 (under the definition and a natural axiomatization) for the graph groupoids K of all “parts” K of G. A loop-reduced finite path generates a semicircular element in graph groupoid algebra. Thus, the existence of semicircular systems acting on the free-probabilistic structure of a given graph G is guaranteed by the existence of loop-reduced finite paths in G. The non-semicircularity induced by graphs yields a new index-like notion called the graph-tree index Γ of G. We study the connections between our graph-tree index and non-semicircular cases. Hence, non-semicircularity also yields the classification of our graphs in terms of a certain type of trees. As an application, we construct towers of graph-groupoid-inclusions which preserve the graph-tree index. We further show that such classification applies to monoidal operads.

APA, Harvard, Vancouver, ISO, and other styles

28

LING, BO, CI XUAN WU, and BEN GONG LOU. "PENTAVALENT SYMMETRIC GRAPHS OF ORDER." Bulletin of the Australian Mathematical Society 90, no. 3 (August 27, 2014): 353–62. http://dx.doi.org/10.1017/s0004972714000616.

Full text

Abstract:

AbstractA complete classification is given of pentavalent symmetric graphs of order$30p$, where$p\ge 5$is a prime. It is proved that such a graph${\Gamma }$exists if and only if$p=13$and, up to isomorphism, there is only one such graph. Furthermore,${\Gamma }$is isomorphic to$\mathcal{C}_{390}$, a coset graph of PSL(2, 25) with${\sf Aut}\, {\Gamma }=\mbox{PSL(2, 25)}$, and${\Gamma }$is 2-regular. The classification involves a new 2-regular pentavalent graph construction with square-free order.

APA, Harvard, Vancouver, ISO, and other styles

29

Wu, Jia, Zhibin Hong, Shirui Pan, Xingquan Zhu, Zhihua Cai, and Chengqi Zhang. "Multi-graph-view subgraph mining for graph classification." Knowledge and Information Systems 48, no. 1 (September 21, 2015): 29–54. http://dx.doi.org/10.1007/s10115-015-0872-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Ma, Tinghuai, Qian Pan, Hongmei Wang, Wenye Shao, Yuan Tian, and Najla Al-Nabhan. "Graph classification algorithm based on graph structure embedding." Expert Systems with Applications 161 (December 2020): 113715. http://dx.doi.org/10.1016/j.eswa.2020.113715.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Gogulamudi, Naga Chandrika, and E. SREENIVASA REDDY. "Graph Classification System using Normalized Graph Convolutional Networks." International Journal of System of Systems Engineering 11, no. 3/4 (2021): 1. http://dx.doi.org/10.1504/ijsse.2021.10041862.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Chandrika, G. Naga, and E. Srinivasa Reddy. "Graph classification system using normalised graph convolutional networks." International Journal of System of Systems Engineering 11, no. 3/4 (2021): 320. http://dx.doi.org/10.1504/ijsse.2021.121461.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Qiangrong, Jiang, and Qiu guang. "Graph kernels combined with the neural network on protein classification." Journal of Bioinformatics and Computational Biology 17, no. 05 (October 2019): 1950030. http://dx.doi.org/10.1142/s0219720019500306.

Full text

Abstract:

At present, most of the researches on protein classification are based on graph kernels. The essence of graph kernels is to extract the substructure and use the similarity of substructures as the kernel values. In this paper, we propose a novel graph kernel named vertex-edge similarity kernel (VES kernel) based on mixed matrix, the innovation point of which is taking the adjacency matrix of the graph as the sample vector of each vertex and calculating kernel values by finding the most similar vertex pair of two graphs. In addition, we combine the novel kernel with the neural network and the experimental results show that the combination is better than the existing advanced methods.

APA, Harvard, Vancouver, ISO, and other styles

34

Ranjan, Ekagra, Soumya Sanyal, and Partha Talukdar. "ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 5470–77. http://dx.doi.org/10.1609/aaai.v34i04.5997.

Full text

Abstract:

Graph Neural Networks (GNN) have been shown to work effectively for modeling graph structured data to solve tasks such as node classification, link prediction and graph classification. There has been some recent progress in defining the notion of pooling in graphs whereby the model tries to generate a graph level representation by downsampling and summarizing the information present in the nodes. Existing pooling methods either fail to effectively capture the graph substructure or do not easily scale to large graphs. In this work, we propose ASAP (Adaptive Structure Aware Pooling), a sparse and differentiable pooling method that addresses the limitations of previous graph pooling architectures. ASAP utilizes a novel self-attention network along with a modified GNN formulation to capture the importance of each node in a given graph. It also learns a sparse soft cluster assignment for nodes at each layer to effectively pool the subgraphs to form the pooled graph. Through extensive experiments on multiple datasets and theoretical analysis, we motivate our choice of the components used in ASAP. Our experimental results show that combining existing GNN architectures with ASAP leads to state-of-the-art results on multiple graph classification benchmarks. ASAP has an average improvement of 4%, compared to current sparse hierarchical state-of-the-art method. We make the source code of ASAP available to encourage reproducible research 1.

APA, Harvard, Vancouver, ISO, and other styles

35

Huang, Xiayuan, Xiangli Nie, and Hong Qiao. "PolSAR Image Feature Extraction via Co-Regularized Graph Embedding." Remote Sensing 12, no. 11 (May 28, 2020): 1738. http://dx.doi.org/10.3390/rs12111738.

Full text

Abstract:

Dimensionality reduction (DR) methods based on graph embedding are widely used for feature extraction. For these methods, the weighted graph plays a vital role in the process of DR because it can characterize the data’s structure information. Moreover, the similarity measurement is a crucial factor for constructing a weighted graph. Wishart distance of covariance matrices and Euclidean distance of polarimetric features are two important similarity measurements for polarimetric synthetic aperture radar (PolSAR) image classification. For obtaining a satisfactory PolSAR image classification performance, a co-regularized graph embedding (CRGE) method by combing the two distances is proposed for PolSAR image feature extraction in this paper. Firstly, two weighted graphs are constructed based on the two distances to represent the data’s local structure information. Specifically, the neighbouring samples are sought in a local patch to decrease computation cost and use spatial information. Next the DR model is constructed based on the two weighted graphs and co-regularization. The co-regularization aims to minimize the dissimilarity of low-dimensional features corresponding to two weighted graphs. We employ two types of co-regularization and the corresponding algorithms are proposed. Ultimately, the obtained low-dimensional features are used for PolSAR image classification. Experiments are implemented on three PolSAR datasets and results show that the co-regularized graph embedding can enhance the performance of PolSAR image classification.

APA, Harvard, Vancouver, ISO, and other styles

36

Nikitin, Filipp, Olexandr Isayev, and Vadim Strijov. "DRACON: disconnected graph neural network for atom mapping in chemical reactions." Physical Chemistry Chemical Physics 22, no. 45 (2020): 26478–86. http://dx.doi.org/10.1039/d0cp04748a.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Pan, Weisen, Jian Li, Lisa Gao, Liexiang Yue, Yan Yang, Lingli Deng, and Chao Deng. "Semantic Graph Neural Network: A Conversion from Spam Email Classification to Graph Classification." Scientific Programming 2022 (January 7, 2022): 1–8. http://dx.doi.org/10.1155/2022/6737080.

Full text

Abstract:

In this study, we propose a method named Semantic Graph Neural Network (SGNN) to address the challenging task of email classification. This method converts the email classification problem into a graph classification problem by projecting email into a graph and applying the SGNN model for classification. The email features are generated from the semantic graph; hence, there is no need of embedding the words into a numerical vector representation. The method performance is tested on the different public datasets. Experiments in the public dataset show that the presented method achieves high accuracy in the email classification test against a few public datasets. The performance is better than the state-of-the-art deep learning-based method in terms of spam classification.

APA, Harvard, Vancouver, ISO, and other styles

38

Jawhari, El Moustafa, Maurice Pouzet, and Ivan Rival. "A Classification of Reflexive Graphs: The use of “Holes”." Canadian Journal of Mathematics 38, no. 6 (December 1, 1986): 1299–328. http://dx.doi.org/10.4153/cjm-1986-066-9.

Full text

Abstract:

The purpose of this article is to develop aspects of a classification theory for reflexive graphs. A first important step was already taken in [2]; throughout we follow, at least the spirit, of the classification theory for ordered sets initiated in [1].For a graph G let V(G) denote its vertex set and E(G) ⊆ V(G) × V(G) its edge set. A graph K is a subgraph of G if V(K) ⊆ V(G) and for a, b ∊ V(K), (a, b) ∊ E(K) just if (a, b) ∊ E(G). The subgraph K of G is a retract of G, and we write K ◅ G, if there is an edge-preserving map g of V(G) to V(K) satisfying g(v) = v for each v ∊ V(K); g is called a retraction. A reflexive graph is an undirected graph with a loop at every vertex. The reason for a loop at a vertex is that an edge-preserving map can send the two vertices of an adjacent pair to it. The concept is illustrated in Figure 1. From here on, though, we shall for convenience suppress the illustration of the loops in the figures of reflexive graphs.

APA, Harvard, Vancouver, ISO, and other styles

39

Power, Stephen C., Igor A. Baburin, and Davide M. Proserpio. "Isotopy classes for 3-periodic net embeddings." Acta Crystallographica Section A Foundations and Advances 76, no. 3 (March 5, 2020): 275–301. http://dx.doi.org/10.1107/s2053273320000625.

Full text

Abstract:

Entangled embedded periodic nets and crystal frameworks are defined, along with their dimension type, homogeneity type, adjacency depth and periodic isotopy type. Periodic isotopy classifications are obtained for various families of embedded nets with small quotient graphs. The 25 periodic isotopy classes of depth-1 embedded nets with a single-vertex quotient graph are enumerated. Additionally, a classification is given of embeddings of n-fold copies of pcu with all connected components in a parallel orientation and n vertices in a repeat unit, as well as demonstrations of their maximal symmetry periodic isotopes. The methodology of linear graph knots on the flat 3-torus [0,1)3 is introduced. These graph knots, with linear edges, are spatial embeddings of the labelled quotient graphs of an embedded net which are associated with its periodicity bases.

APA, Harvard, Vancouver, ISO, and other styles

40

Tsiovkina, Ludmila Yu. "ON A CLASS OF EDGE-TRANSITIVE DISTANCE-REGULAR ANTIPODAL COVERS OF COMPLETE GRAPHS." Ural Mathematical Journal 7, no. 2 (December 30, 2021): 136. http://dx.doi.org/10.15826/umj.2021.2.010.

Full text

Abstract:

The paper is devoted to the problem of classification of edge-transitive distance-regular antipodal covers of complete graphs. This extends the classification of those covers that are arc-transitive, which has been settled except for some tricky cases that remain to be considered, including the case of covers satisfying condition $c_2=1$ (which means that every two vertices at distance 2 have exactly one common neighbour).Here it is shown that an edge-transitive distance-regular antipodal cover of a complete graph with $c_2=1$ is either the second neighbourhood of a vertex in a Moore graph of valency 3 or 7, or a Mathon graph, or a half-transitive graph whose automorphism group induces an affine $2$-homogeneous group on the set of its fibres. Moreover, distance-regular antipodal covers of complete graphs with $c_2=1$ that admit an automorphism group acting $2$-homogeneously on the set of fibres (which turns out to be an approximation of the property of edge-transitivity of such cover), are described. A well-known correspondence between distance-regular antipodal covers of complete graphs with $c_2=1$ and geodetic graphs of diameter two that can be viewed as underlying graphs of certain Moore geometries, allows us to effectively restrict admissible automorphism groups of covers under consideration by combining Kantor's classification of involutory automorphisms of these geometries together with the classification of finite 2-homogeneous permutation groups.

APA, Harvard, Vancouver, ISO, and other styles

41

Yao, Huaxiu, Chuxu Zhang, Ying Wei, Meng Jiang, Suhang Wang, Junzhou Huang, Nitesh Chawla, and Zhenhui Li. "Graph Few-Shot Learning via Knowledge Transfer." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 6656–63. http://dx.doi.org/10.1609/aaai.v34i04.6142.

Full text

Abstract:

Towards the challenging problem of semi-supervised node classification, there have been extensive studies. As a frontier, Graph Neural Networks (GNNs) have aroused great interest recently, which update the representation of each node by aggregating information of its neighbors. However, most GNNs have shallow layers with a limited receptive field and may not achieve satisfactory performance especially when the number of labeled nodes is quite small. To address this challenge, we innovatively propose a graph few-shot learning (GFL) algorithm that incorporates prior knowledge learned from auxiliary graphs to improve classification accuracy on the target graph. Specifically, a transferable metric space characterized by a node embedding and a graph-specific prototype embedding function is shared between auxiliary graphs and the target, facilitating the transfer of structural knowledge. Extensive experiments and ablation studies on four real-world graph datasets demonstrate the effectiveness of our proposed model and the contribution of each component.

APA, Harvard, Vancouver, ISO, and other styles

42

Aalipour, G., S. Akbari, M. Behboodi, R. Nikandish, M. J. Nikmehr, and F. Shaveisi. "The Classification of the Annihilating-Ideal Graphs of Commutative Rings." Algebra Colloquium 21, no. 02 (April 11, 2014): 249–56. http://dx.doi.org/10.1142/s1005386714000200.

Full text

Abstract:

Let R be a commutative ring and 𝔸(R) be the set of ideals with non-zero annihilators. The annihilating-ideal graph of R is defined as the graph 𝔸𝔾(R) with the vertex set 𝔸(R)* = 𝔸(R)\{(0)} and two distinct vertices I and J are adjacent if and only if IJ = (0). Here, we present some results on the clique number and the chromatic number of the annihilating-ideal graph of a commutative ring. It is shown that if R is an Artinian ring and ω (𝔸𝔾(R)) = 2, then R is Gorenstein. Also, we investigate commutative rings whose annihilating-ideal graphs are complete or bipartite.

APA, Harvard, Vancouver, ISO, and other styles

43

Zhang, Chaozi, Jianli Wang, and Kainan Yao. "Global Random Graph Convolution Network for Hyperspectral Image Classification." Remote Sensing 13, no. 12 (June 10, 2021): 2285. http://dx.doi.org/10.3390/rs13122285.

Full text

Abstract:

Machine learning and deep learning methods have been employed in the hyperspectral image (HSI) classification field. Of deep learning methods, convolution neural network (CNN) has been widely used and achieved promising results. However, CNN has its limitations in modeling sample relations. Graph convolution network (GCN) has been introduced to HSI classification due to its demonstrated ability in processing sample relations. Introducing GCN into HSI classification, the key issue is how to transform HSI, a typical euclidean data, into non-euclidean data. To address this problem, we propose a supervised framework called the Global Random Graph Convolution Network (GR-GCN). A novel method of constructing the graph is adopted for the network, where the graph is built by randomly sampling from the labeled data of each class. Using this technique, the size of the constructed graph is small, which can save computing resources, and we can obtain an enormous quantity of graphs, which also solves the problem of insufficient samples. Besides, the random combination of samples can make the generated graph more diverse and make the network more robust. We also use a neural network with trainable parameters, instead of artificial rules, to determine the adjacency matrix. An adjacency matrix obtained by a neural network is more flexible and stable, and it can better represent the relationship between nodes in a graph. We perform experiments on three benchmark datasets, and the results demonstrate that the GR-GCN performance is competitive with that of current state-of-the-art methods.

APA, Harvard, Vancouver, ISO, and other styles

44

FANG, XIN GUI, JIE WANG, and SANMING ZHOU. "CLASSIFICATION OF TETRAVALENT -TRANSITIVE NONNORMAL CAYLEY GRAPHS OF FINITE SIMPLE GROUPS." Bulletin of the Australian Mathematical Society 104, no. 2 (January 11, 2021): 263–71. http://dx.doi.org/10.1017/s0004972720001446.

Full text

Abstract:

AbstractA graph $\Gamma $ is called $(G, s)$ -arc-transitive if $G \le \text{Aut} (\Gamma )$ is transitive on the set of vertices of $\Gamma $ and the set of s-arcs of $\Gamma $ , where for an integer $s \ge 1$ an s-arc of $\Gamma $ is a sequence of $s+1$ vertices $(v_0,v_1,\ldots ,v_s)$ of $\Gamma $ such that $v_{i-1}$ and $v_i$ are adjacent for $1 \le i \le s$ and $v_{i-1}\ne v_{i+1}$ for $1 \le i \le s-1$ . A graph $\Gamma $ is called 2-transitive if it is $(\text{Aut} (\Gamma ), 2)$ -arc-transitive but not $(\text{Aut} (\Gamma ), 3)$ -arc-transitive. A Cayley graph $\Gamma $ of a group G is called normal if G is normal in $\text{Aut} (\Gamma )$ and nonnormal otherwise. Fang et al. [‘On edge transitive Cayley graphs of valency four’, European J. Combin.25 (2004), 1103–1116] proved that if $\Gamma $ is a tetravalent 2-transitive Cayley graph of a finite simple group G, then either $\Gamma $ is normal or G is one of the groups $\text{PSL}_2(11)$ , ${\rm M} _{11}$ , $\text{M} _{23}$ and $A_{11}$ . However, it was unknown whether $\Gamma $ is normal when G is one of these four groups. We answer this question by proving that among these four groups only $\text{M} _{11}$ produces connected tetravalent 2-transitive nonnormal Cayley graphs. We prove further that there are exactly two such graphs which are nonisomorphic and both are determined in the paper. As a consequence, the automorphism group of any connected tetravalent 2-transitive Cayley graph of any finite simple group is determined.

APA, Harvard, Vancouver, ISO, and other styles

45

Jia Wu, Shirui Pan, Xingquan Zhu, and Zhihua Cai. "Boosting for Multi-Graph Classification." IEEE Transactions on Cybernetics 45, no. 3 (March 2015): 416–29. http://dx.doi.org/10.1109/tcyb.2014.2327111.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Zhan, Zikang. "Performance of Different Graph Neural Networks on Graph Classification." Journal of Physics: Conference Series 1607 (August 2020): 012091. http://dx.doi.org/10.1088/1742-6596/1607/1/012091.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Shirui Pan, Jia Wu, Xingquan Zhu, and Chengqi Zhang. "Graph Ensemble Boosting for Imbalanced Noisy Graph Stream Classification." IEEE Transactions on Cybernetics 45, no. 5 (May 2015): 954–68. http://dx.doi.org/10.1109/tcyb.2014.2341031.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Xiao, Fei, Yi Sun, Donggao Du, Xuelei Li, and Min Luo. "A Novel Malware Classification Method Based on Crucial Behavior." Mathematical Problems in Engineering 2020 (March 21, 2020): 1–12. http://dx.doi.org/10.1155/2020/6804290.

Full text

Abstract:

Recently, some graph-based methods have been proposed for malware detection. However, current malware is generally characterized by sophisticated behaviors, which makes graph-based malware detection extremely challenging. To address this issue, we propose a graph repartition algorithm by transforming API call graphs into fragment behaviors based on programs’ dynamic execution traces. The proposed algorithm relies on the N-order subgraph (NSG) for constructing the appropriate fragment behavior. Moreover, we improve the term frequency-inverse document frequency- (TF-IDF-) like measure and information gain (IG) to extract the crucial N-order subgraph (CNSG). This novel behavioral representation and improved extraction method can accurately represent crucial behaviors of malware. Experiments on 4,400 samples demonstrate that the proposed method achieves a high accuracy of 99.75% in malware detection and promising performance of 95.27% in malware classification.

APA, Harvard, Vancouver, ISO, and other styles

49

Ma, Tinghuai, Wenye Shao, Yongsheng Hao, and Jie Cao. "Graph classification based on graph set reconstruction and graph kernel feature reduction." Neurocomputing 296 (June 2018): 33–45. http://dx.doi.org/10.1016/j.neucom.2018.03.029.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Chen, Yunxiao, Xiaoou Li, Jingchen Liu, Gongjun Xu, and Zhiliang Ying. "Exploratory Item Classification Via Spectral Graph Clustering." Applied Psychological Measurement 41, no. 8 (February 1, 2017): 579–99. http://dx.doi.org/10.1177/0146621617692977.

Full text

Abstract:

Large-scale assessments are supported by a large item pool. An important task in test development is to assign items into scales that measure different characteristics of individuals, and a popular approach is cluster analysis of items. Classical methods in cluster analysis, such as the hierarchical clustering, K-means method, and latent-class analysis, often induce a high computational overhead and have difficulty handling missing data, especially in the presence of high-dimensional responses. In this article, the authors propose a spectral clustering algorithm for exploratory item cluster analysis. The method is computationally efficient, effective for data with missing or incomplete responses, easy to implement, and often outperforms traditional clustering algorithms in the context of high dimensionality. The spectral clustering algorithm is based on graph theory, a branch of mathematics that studies the properties of graphs. The algorithm first constructs a graph of items, characterizing the similarity structure among items. It then extracts item clusters based on the graphical structure, grouping similar items together. The proposed method is evaluated through simulations and an application to the revised Eysenck Personality Questionnaire.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Graph classification'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles