检索结果-内蒙古大学图书馆

Normalized graph compression distance - A novel graph matching framework

pattern recognition LETTERS 2025年 190卷 97-104页

作者： Gillioz, Anthony Riesen, Kaspar Univ Bern Inst Comp Sci Neubruckstr 10 CH-3012 Bern Switzerland

Computing dissimilarities between pairs of graphs is a common task in many pattern recognition applications. A widely used method to accomplish this task is graph edit distance (GED). However, computation of exact GED is challenging due to its exponential time complexity with respect to the size of the underlying graphs. The major contribution of the present paper is that we introduce a complementary - and much faster - method to compute dissimilarities between pairs of graphs. Our novel framework involves a compressor-based metric that is adapted to the graph domain. Basically, the compressor-based metric identifies regularities in compressed graphs and assigns smaller distances to pairs of graphs that are comparable and are thus assumed to belong to the same class. To assess the effectiveness of the proposed graph matching framework, we perform a series of evaluations on eleven real-world datasets. It turns out that the novel matching framework performs equally well as, or even better than, GED, yet with significantly lower computation time.

关键词： graph-based pattern recognition graph Matching graph Compression

来源：评论

学校读者我要写书评

暂无评论

GL2vec: graph Embedding Enriched by Line graphs with Edge Features 26th

GL2vec: Graph Embedding Enriched by Line Graphs with Edge Fe...

引用

26th International Conference on Neural Information Processing (ICONIP) of the Asia-Pacific-Neural-Network-Society (APNNS)

作者： Chen, Hong Koga, Hisashi Univ Electrocommun Grad Sch Informat & Engn Tokyo 1828585 Japan

ISBN: (纸本)9783030367183;9783030367176

Recently, several techniques to learn the embedding for a given graph dataset have been proposed. Among them, graph2vec is significant in that it unsupervisedly learns the embedding of entire graphs which is useful for graph classification. This paper develops an algorithm which improves graph2vec. First, we point out two limitations of graph2vec: (1) Edge labels cannot be handled and (2) graph2vec does not always preserve structural information enough to evaluate the structural similarity, because it bundles the node label information and the structural information in extracting subgraphs. Our algorithm overcomes these limitations by exploiting the line graphs (edge-to-vertex dual graphs) of given graphs. Specifically, it complements either the edge label information or the structural information which graph2vec misses with the embeddings of the line graphs. Our method is named as GL2vec (graph and Line graph to vector) because it concatenates the embedding of an original graph to that of the corresponding line graph. Experimentally, GL2vec achieves significant improvements in graph classification task over graph2vec for many benchmark datasets.

关键词： Line graph graph embedding graph-based pattern recognition

来源：评论

学校读者我要写书评

暂无评论

A Granular Computing approach to the design of optimized graph classification systems

引用

SOFT COMPUTING 2014年第2期18卷 393-412页

作者： Bianchi, Filippo Maria Livi, Lorenzo Rizzi, Antonello Sadeghian, Alireza Univ Roma La Sapienza Dept Informat Engn Elect & Telecommun I-00184 Rome Italy Ryerson Univ Dept Comp Sci Toronto ON M5B 2K3 Canada

Research on graph-based pattern recognition and Soft Computing systems has attracted many scientists and engineers in several different contexts. This fact is motivated by the reason that graphs are general structures able to encode both topological and semantic information in data. While the data modeling properties of graphs are of indisputable power, there are still different concerns about the best way to compute similarity functions in an effective and efficient manner. To this end, suited transformation procedures are usually conceived to address the well-known Inexact graph Matching problem in an explicit embedding space. In this paper, we propose two graph embedding algorithms based on the Granular Computing paradigm, which are engineered as key procedures of a general-purpose graph classification system. Tests have been conducted on benchmarking datasets relying on both synthetic and real-world data, achieving competitive results in terms of test set classification accuracy.

关键词： graph-based pattern recognition Granular Computing Granular modeling Inexact graph Matching graph embedding

来源：评论

学校读者我要写书评

暂无评论

引用

INFORMATION SCIENCES 2014年 266卷 47-64页

作者： Livi, Lorenzo Rizzi, Antonello Sadeghian, Alireza Univ Roma La Sapienza Dept Informat Engn Elect & Telecommun I-00184 Rome Italy Ryerson Univ Dept Comp Sci Toronto ON M5B 2K3 Canada

This paper introduces a new general-purpose classification system able to face automatically a wide range of classification problems for labeled graphs. The proposed graph classifier explicitly embeds the input labeled graphs using the dissimilarity representation framework. We developed a method to optimize the dissimilarity space representation estimating the quadratic Renyi entropy of the underlying distribution of the generated dissimilarity values. The global optimization governing the synthesis of the classifier is implemented using a genetic algorithm and it is carried out by means of two operations that perform prototype selection and extraction on the input set of graphs. During the optimization step, we adopted a suitable objective function which includes the classification accuracy achieved by the whole classification model on a validation set. Experimental evaluations have been conducted on both synthetic and well-known benchmarking datasets, achieving competitive test set classification accuracy results with respect to other state-of-the-art graph embedding based classification systems. (C) 2014 Elsevier Inc. All rights reserved.

来源：评论

学校读者我要写书评

暂无评论

The graph matching problem

引用

pattern ANALYSIS AND APPLICATIONS 2013年第3期16卷 253-283页

作者： Livi, Lorenzo Rizzi, Antonello Univ Roma La Sapienza I-00185 Rome Italy

In this paper, we propose a survey concerning the state of the art of the graph matching problem, conceived as the most important element in the definition of inductive inference engines in graph-based pattern recognition applications. We review both methodological and algorithmic results, focusing on inexact graph matching procedures. We consider different classes of graphs that are roughly differentiated considering the complexity of the defined labels for both vertices and edges. Emphasis will be given to the understanding of the underlying methodological aspects of each identified research branch. A selection of inexact graph matching algorithms is proposed and synthetically described, aiming at explaining some significant instances of each graph matching methodology mainly considered in the technical literature.

关键词： graph-based pattern recognition Inexact graph matching graph edit distance graph kernels graph embedding

来源：评论

学校读者我要写书评

暂无评论

Matching of Time-Varying Labeled graphs

Matching of Time-Varying Labeled Graphs

引用

International Joint Conference on Neural Networks (IJCNN)

作者： Bianchi, Filippo Maria Livi, Lorenzo Rizzi, Antonello Univ Roma La Sapienza Dept Informat Engn Elect & Telecommun I-00184 Rome Italy

ISBN: (纸本)9781467361293;9781467361286

In this paper we propose an inexact graph matching algorithm which computes the dissimilarity of a time-varying labeled graph with respect to a static one. This approach is specifically designed for processing very large labeled graphs, which are subject to frequent edit operations that modify the topology and the labeling of restricted zones of the graph. In this scenario, repeating each time an extensive computation of the whole dissimilarity value would require too much time;moreover, since only a specific part of the graph changes, it would result also in a waste of computations. We propose a fast approach for computing the graph dissimilarity which exploits the dissimilarity value estimated in the previous time interval and the nature of the observed edit operations. We evaluate the properties of the proposed approach with respect to well-known graph matching algorithms, by simulating the dynamics of the graph. Overall, the experiments confirm the effectiveness of the approach.

关键词： Time-varying labeled graphs Dynamical systems Inexact graph matching graph edit distance graph-based pattern recognition

来源：评论

学校读者我要写书评

暂无评论

引用

International Joint Conference on Neural Networks (IJCNN)

作者： Livi, Lorenzo Bianchi, Filippo Maria Rizzi, Antonello Sadeghian, Alireza Univ Roma La Sapienza Dept Informat Engn Elect & Telecommun Rome Italy Ryerson Univ Dept Comp Sci Toronto ON Canada

ISBN: (纸本)9781467361293;9781467361286

We propose two variants of a general-purpose graph classification system which rely on a theoretical result that we prove in this paper. The result allows us to solve analytically the setting of a sequential clustering algorithm that is used for compressing the input labeled graphs represented in the dissimilarity space. As a consequence, we achieve a considerable asymptotic and practical speed-up of the overall classification system, maintaining state-of-the-art results in terms of test set classification accuracy on well-known benchmarking datasets of labeled graphs. The obtained speed-up makes the system one step closer towards the applicability to bigger labeled graphs and larger datasets.

关键词： graph-based pattern recognition Information-theoretic descriptors Dissimilarity representation Cluster analysis

来源：评论

学校读者我要写书评

暂无评论

Matching of Time-Varying Labeled graphs

Matching of Time-Varying Labeled Graphs

引用

International Joint Conference on Neural Networks

作者： Filippo Maria Bianchi Lorenzo Livi Antonello Rizzi Department of Information Engineering Electronics and Telecommunications at SAPIENZA University of Rome Via Eudossiana 18 00184 Rome Italy

ISBN: (纸本)9781467361279

关键词： Time-varying labeled graphs Dynamical systems Inexact graph matching graph edit distance graph-based pattern recognition graph matching DYNAMICAL SYSTEMS Line graph time varying graph editing

来源：评论

学校读者我要写书评

暂无评论

引用

International Joint Conference on Neural Networks

作者： Lorenzo Livi Filippo Maria Bianchi Antonello Rizzi Alireza Sadeghian Department of Information Engineering Electronics and Telecommunications at SAPIENZA University of Rome Italy Department of Computer Science at Ryerson University Toronto Canada

ISBN: (纸本)9781467361279

关键词： graph-based pattern recognition Information theoretic descriptors Dissimilarity representation Cluster analysis Cluster Analysis Speeding Clustering algorithms embedding Dataset labelled graph Solve Analytically closer

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：