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

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

来源：评论

学校读者我要写书评

暂无评论

Mining structure overlaps for efficient graph compression

引用

INTERNATIONAL JOURNAL OF DATA SCIENCE AND ANALYTICS 2025年 1-14页

作者： Pitois, Francois Seba, Hamida Haddad, Mohammed Univ Lyon INSA Lyon CNRS UCBLLIRISUMR5205 F-69622 Villeurbanne France Univ Bourgogne LIB EA 7534 F-21000 Dijon France

Several graph compression approaches rely on finding dense structures such as cliques or quasi-cliques which are simple to encode, i.e., they are defined by the set of their vertices. The graph is then encoded by its structures. However, existing methods consider these structures at a high level ignoring overlaps. This leads to encoding multiple times the overlapping parts of the considered structures, which is redundant. To deal with this issue, we propose to dig deep into the structures, to identify these overlappings so as to avoid redundant encoding. Hence, we develop algorithms to construct highly compressed graph representations. We tested our algorithms on several graph datasets, and our results outperform state of the art methods.

关键词： graph compression graph summarizing graph partitioning Structure mining

来源：评论

学校读者我要写书评

暂无评论

Self-Attention Enhanced Auto-Encoder for Link Weight Prediction With graph compression

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2024年第1期11卷 89-99页

作者： Liu, Zhen Zuo, Wenbo Zhang, Dongning Zhou, Chuan Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Peoples R China 54th Res Inst CETC Shijiazhuang 050081 Peoples R China Chinese Acad Sci Acad Math & Syst Sci Beijing 100045 Peoples R China

Predicting unobservable or missing weights over links on various real-world networks is of fundamental scientific significance in disparate disciplines like sociology, biology, and physics, as it has been revealed by scientists that link weights, representing strong or weak ties, are able to help us understand the mechanism of link formation, community growth, and network evolution. Nevertheless, previous studies mainly relied on shallow graph features to fulfill the task of link weight prediction and thus the proposed models have relatively poor predictive performance. By learning deep graph features to improve the predictive capability, a Self-attention Enhanced graph Auto-encoder called SEA is proposed. To resolve the challenge of the model's scalability for large graph applications, a two-phased link weight prediction framework is further proposed, which comprises the modules of graph compression and SEA. Experiments on seven real-world networks (four uncompressed networks and three compressed networks) demonstrated that SEA can achieve an average 6% improvement of accuracy in missing link weight prediction against state-of-the-art methods. Some extended experiments and analyses verified that the proposed framework can significantly reduce the network's size by 60%-80% while maintaining the predictive power.

关键词： Predictive models Proteins Task analysis Evolution (biology) Computational modeling Visualization Time complexity Auto-encoder graph compression link weight prediction self-attention mechanism

来源：评论

学校读者我要写书评

暂无评论

EGC2: Enhanced graph classification with easy graph compression

引用

INFORMATION SCIENCES 2023年第1期629卷 376-397页

作者： Chen, Jinyin Xiong, Haiyang Zheng, Haibin Zhang, Dunjie Zhang, Jian Jia, Mingwei Liu, Yi Zhejiang Univ Technol Inst Cyberspace Secur Hangzhou 310023 Peoples R China Zhejiang Univ Technol Coll Informat Engn Hangzhou 310023 Peoples R China Hangzhou Dianzi Univ Sch Cyberspace Secur Hangzhou 310000 Peoples R China Zhejiang Univ Technol Inst Proc Equipment & Control Engn Hangzhou 310023 Peoples R China

graph classification is crucial in network analyses. Networks face potential security threats, such as adversarial attacks. Some defense methods may trade off the algorithm complexity for robustness, such as adversarial training, whereas others may trade off clean example performance, such as smoothing-based defense. Most suffer from high complexity or low transferability. To address this problem, we proposed EGC2, an enhanced graph classification model with easy graph compression. EGC2 captures the relationship between the features of different nodes by constructing feature graphs and improving the aggregation of the node-level representations. To achieve lower-complexity defense applied to graph classification models, EGC2 utilizes a centrality-based edge-importance index to compress the graphs, filtering out trivial structures and adversarial perturbations in the input graphs, thus improving the model's robustness. Experiments on ten benchmark datasets demonstrate that the proposed feature read-out and graph compression mechanisms enhance the robustness of multiple basic models, resulting in a state-of-the-art performance in terms of accuracy and robustness against various adversarial attacks.

关键词： graph classification Adversarial attack graph compression Feature aggregation Robustness

来源：评论

学校读者我要写书评

暂无评论

GCSTI: A Single-Cell Pseudotemporal Trajectory Inference Method Based on graph compression

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2023年第5期20卷 2945-2958页

作者： Tu, Wenhui Ling, Guang Liu, Feng Hu, Fuyan Song, Xiangxiang Wuhan Univ Technol Sch Sci Wuhan 430070 Peoples R China

The single-cell pseudotemporal trajectory inference is an important way to explore the process of developmental changes within a cell. Due to the uneven rate of cell growth, changes in gene expression depend less on the time of data collection and more on a cell's "internal clock". To overcome the challenges of gene analysis, and replicate biological developmental processes, several strategies have been put forth. However, due to the size of single-cell datasets, locating relevant signposts usually necessitate clustering analysis or a sizable amount of priori information. To this end, we propose a novel single-cell pseudotemporal trajectory inference technique: GCSTI method, which is based on graph compression and doesn't rely on a priori knowledge or clustering procedures, can handle the trajectory inference problem for a large network in a stable and efficient manner. Additionally, we simultaneously improve the pseudotime defining method currently employed in this study in order to obtain more trustworthy and beneficial outcomes for trajectory inference. Finally, we validate the efficacy and stability of the GCSTI method using datasets from human skeletal muscle myogenic cells and four simulated datasets.

关键词： graph compression pseudotime definition pseudotemporal trajectory inference single-cell data

来源：评论

学校读者我要写书评

暂无评论

GCDroid: Android Malware Detection Based on graph compression With Reachability Relationship Extraction for IoT Devices

引用

IEEE INTERNET OF THINGS JOURNAL 2023年第13期10卷 11343-11356页

作者： Niu, Weina Wang, Yihang Liu, Xingyu Yan, Ran Li, Xiong Zhang, Xiaosong Univ Elect Sci & Technol China Inst Cyber Secur Sch Comp Sci & Engn Chengdu 611731 Peoples R China

With the widespread popularity of Internet of Things (IoT) devices based on the Android system, the amount of Android malware targeting IoT devices continues to increase, causing great economic losses. Accordingly, efficient and accurate Android malware detection methods are particularly important. Recently, many Android malware detection and classification methods have been proposed, but most of them ignore the deep relationships among software. In this article, we propose a graph compression algorithm with reachability relationship extraction (GCRR) and design an Android malware detection and classification method called GCDroid based on this algorithm. A theoretical analysis shows that GCRR can reasonably extract the reachability relationships among APKs and compress a large heterogeneous APK-API relationship graph into a homogeneous APKs graph. Experiments show that GCDroid based on GCRR greatly reduces the required time consumption while improving detection accuracy. Compared with the existing excellent static Android malware detection methods, GCDroid improves upon their detection accuracies by 1.53%-39.13% on different data sets and outperforms the benchmark methods in terms of Android malware classification. Furthermore, compared with those of the baseline methods that are similar to GCDroid, GCDroid's time consumption for model training and other aspects is only one-tenth as high or even less.

关键词： Android malware detection and classification APK application programming interface (API) graph compression reachability relationship

来源：评论

学校读者我要写书评

暂无评论

ITR: Grammar-based graph compression supporting fast triple queries.

ITR: Grammar-based graph compression supporting fast triple ...

引用

Data compression Conference (DCC)

作者： Adler, Enno Boettcher, Stefan Hartel, Rita Paderborn Univ Paderborn Germany

ISBN: (纸本)9798350385885;9798350385878

Neighborhood queries are the most common queries on graphs;thus, it is desirable to answer them efficiently on compressed data structures. Our full paper [1] presents a grammar-based compressor called Incidence-Type-RePair (ITR) for graphs with labeled nodes and labeled edges based on RePair. We applied ITR to network, version, and RDF graphs and we compared the performance of triple SPO queries on these compressed datasets generated by ITR and 4 state-of-the-art graph compression approaches. As shown in the figure below and in our full paper [1] , ITR outperforms the other graph compressors for all triple SPO queries except for the query-type ? P ?, while providing a compression size comparable to the other compressors. Thereby, ITR is 2 to 6 times faster than the fastest compared query-evaluation technique and up to 100 times faster than the slowest approach in our tests. © 2024 IEEE.

关键词： grammar-based compression graph compression hyperenge-replacement grammar neighborhood queries queries on compressed data self-indexes

来源：评论

学校读者我要写书评

暂无评论

引用

33rd IEEE International Conference on Computer Communications and Networks (ICCCN)

作者： Akin, Hamdi Selim Aktas, Mehmet Emin Islam, Muhammed Ifte Hossain, Tanvir Akbas, Esra Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Georgia State Univ Inst Insight Atlanta GA 30303 USA

ISBN: (纸本)9798350348439;9798350384611

Network analysis is an emerging field with a wide spectrum of applications across many disciplines such as social networks, computer networks, and healthcare. However, the ever-increasing size of real-world networks is a major challenge for network analysis due to their high computational and space costs. In this paper, we utilize a node similarity-based graph compression method, SGC, and investigate the effect of various node similarity measures on graph compression. SGC compresses the input graph to a smaller graph without losing any/much information about its global structure and the local proximity of its vertices. We apply our compression method to the network embedding problem to study its effectiveness and efficiency. Our experimental results on four real-world networks show that each similarity measure has a different effect on graph compression and embedding, where some yield an improvement up to 70% network embedding time without decreasing classification accuracy as evaluated on single and multi-label classification tasks.

关键词： graph compression network embedding node similarity node classification

来源：评论

学校读者我要写书评

暂无评论

graph compression based on transitivity for neighborhood query

引用

INFORMATION SCIENCES 2021年 576卷 312-328页

作者： Nejad, Amin Emamzadeh Esmaeili Jahromi, Mansoor Zolghadri Taheri, Mohammad Shiraz Univ Dept Comp Sci & Engn Shiraz Iran

In recent years, many graph compression methods have been introduced. One successful category of them is based on local decompression designed to answer neighborhood queries. These techniques mainly rely on local similarities of vertices. Besides, their perfor-mance is usually a function of graph sparsity. The proposed approach, in this paper, is a lossy compression technique used to answer neighborhood queries with a more general precondition, called transitivity. The output of this method is a sparse graph optimized to keep original adjacent vertices, in at most 2-distance from each other and vice versa. In other words, by traversing a compressed graph by depth of 2, from any desired vertex, its original adjacency list is reconstructed, with an acceptable error. This paper models an optimization problem to solve the inverse problem of finding the best compressed graph in order to minimize the reconstruction error. Then, this NP problem is approximated by a heuristic with a low degree polynomial time-complexity near to the complexity of the for-ward problem. The results of applying the proposed method on toy and real datasets are compared with the state of the art that improves compression ratio and performance with an acceptable query response time. (c) 2021 Elsevier Inc. All rights reserved.

关键词： graph compression Local decompression Neighborhood query Reachability query Transitivity

来源：评论

学校读者我要写书评

暂无评论

A Fine-Grained Structural Partitioning Approach to graph compression 25th

A Fine-Grained Structural Partitioning Approach to Graph Com...

引用

25th International Conference on Big Data Analytics and Knowledge Discovery (DaWaK)

作者： Pitois, Francois Seba, Hamida Haddad, Mohammed Univ Lyon UCBL CNRS INSA LyonUMR 5205LIRIS F-69622 Villeurbanne France Univ Bourgogne LIB EA 7534 Dijon France

ISBN: (纸本)9783031398308;9783031398315

To compress a graph, some methods rely on finding highly compressible structures, such as very dense subgraphs, and encode a graph by listing these structures compressed. However, structures can overlap, leading to encoding the same information multiple times. The method we propose deals with this issue, by identifying overlaps and encoding them only once. We have tested our method on various real-world graphs. The obtained results show that our approach is efficient and outperforms state of the art methods. The source code of our algorithms, together with some sample input instances, are available at https://***/fpitois/***.

关键词： graph compression graph summarising graph partitioning graph mining

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：