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

Robust Size Estimation of Online Social Networks via subgraph sampling

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2020年第4期7卷 2702-2713页

作者： Jiang, Yangfan Fu, Yao Zhou, Yipeng Wu, Di Sun Yat Sen Univ Sch Data & Comp Sci Guangzhou 510006 Peoples R China Guangdong Key Lab Big Data Anal & Proc Guangzhou 510006 Peoples R China Sun Yat Sen Univ Key Lab Machine Intelligence & Adv Comp Minist Educ Guangzhou 510006 Guangdong Peoples R China Macquarie Univ Dept Comp Fac Sci & Engn Macquarie Pk NSW 2109 Australia

Estimating the number of nodes in a large-scale online social network is a fundamental problem in the field of network science. However, it is observed that the performance of traditional RW (Random Walk)-based network size estimators is not stable enough. The relative error of estimated network size can be extremely high for social networks with high skewness of degree distribution, even when the sampling rate is over 50%. In this paper, we propose a robust network size estimation algorithm called Graser, which significantly improves the robustness of size estimation on different types of online social networks. To understand the problem, we first conduct an in-depth study to examine influential factors that lead to inaccuracy of traditional RW-based estimators. Our study identifies a few key factors (e.g., degree distribution) closely related to the inaccuracy of size estimation. Next, we design an efficient network size estimator called Graser, which can iteratively reduce the estimation error by subgraph sampling. We also perform theoretical analysis on the performance of Graser, and prove that our algorithm can guarantee to achieve a relative error that is much smaller than that of traditional RW-based estimators. Finally, we conduct extensive experiments using real datasets to evaluate the performance of our proposed algorithm and the results show that Graser performs much better than traditional RW-based estimators on different types of social networks, and can reduce the relative error of size estimation significantly even with an extremely low sampling rate.

关键词： Size estimation online social networks subgraph sampling

来源：评论

学校读者我要写书评

暂无评论

Join sampling Under Acyclic Degree Constraints and (Cyclic) subgraph sampling 27

Join Sampling Under Acyclic Degree Constraints and (Cyclic) ...

引用

27th International Conference on Database Theory (ICDT)

作者： Wang, Ru Tao, Yufei Chinese Univ Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9783959773126

Given a (natural) join with an acyclic set of degree constraints (the join itself does not need to be acyclic), we show how to draw a uniformly random sample from the join result in O(polymat/ max{1, OUT}) expected time (assuming data complexity) after a preprocessing phase of O(IN) expected time, where IN, OUT, and polymat are the join's input size, output size, and polymatroid bound, respectively. This compares favorably with the state of the art (Deng et al. and Kim et al., both in PODS'23), which states that, in the absence of degree constraints, a uniformly random sample can be drawn in (O) over tilde (AGM/ max{1, OUT}) expected time after a preprocessing phase of (O) over tilde (IN) expected time, where AGM is the join's AGM bound and (O) over tilde (.) hides a polylog(IN) factor. Our algorithm applies to every join supported by the solutions of Deng et al. and Kim et al. Furthermore, since the polymatroid bound is at most the AGM bound, our performance guarantees are never worse, but can be considerably better, than those of Deng et al. and Kim et al. We then utilize our techniques to tackle directed subgraph sampling, a problem that has extensive database applications and bears close relevance to joins. Let G = ( V, E) be a directed data graph where each vertex has an out-degree at most lambda, and let P be a directed pattern graph with a constant number of vertices. The objective is to uniformly sample an occurrence of P in G. The problem can be modeled as join sampling with input size IN = Theta(|E|) but, whenever P contains cycles, the converted join has cyclic degree constraints. We show that it is always possible to throw away certain degree constraints such that (i) the remaining constraints are acyclic and (ii) the new join has asymptotically the same polymatroid bound polymat as the old one. Combining this finding with our new join sampling solution yields an algorithm to sample from the original (cyclic) join (thereby yielding a uniformly random occ

关键词： Join sampling subgraph sampling Degree Constraints Polymatroid Bounds

来源：评论

学校读者我要写书评

暂无评论

A subgraph sampling method for training large-scale graph convolutional network

引用

INFORMATION SCIENCES 2023年 649卷

作者： Zhang, Qi Sun, Yanfeng Hu, Yongli Wang, Shaofan Yin, Baocai Beijing Univ Technol Fac Informat Technol Beijing Key Lab Multimedia & Intelligent Software Beijing 100124 Peoples R China

Graph Convolutional Network (GCN) is a powerful model for graph representation learning. Since GCN updates nodes with a recursive neighbor aggregation scheme, training GCN on large-scale graphs suffers from enormous computational cost and large memory requirement. The subgraph sampling method trains GCN on sampled small-scale subgraphs to speed up GCN. However, they also suffer from problems, such as training GCN on unconnected and scale-unbalanced subgraphs, which reduce performance and efficiency. Moreover, existing subgraph sampling methods train GCN on subgraphs independently and ignore the relation information among different subgraphs. This paper proposes a novel subgraph sampling method, Improved Adaptive Neighbor sampling (IANS), and a novel loss function, subgraph Contrastive Loss. subgraphs sampled by the IANS method are scale-balanced, inside nodes are significantly relevant, and the sample ratio controls the sparsity of subgraphs. To recover the lost relation information between different subgraphs, the subgraph Contrastive Loss is defined, which constrains the initially connected nodes in different subgraphs to be closer and pushes unconnected nodes far away in feature space. A series of experiments are conducted, which train GCN with IANS and subgraph Contrastive Loss for node classification on three different scale datasets. The training time and classification accuracy demonstrate the effectiveness of the proposed method.

关键词： Large-scale graph Graph convolutional network subgraph sampling subgraph contrastive loss Node classification

来源：评论

学校读者我要写书评

暂无评论

Graph Anomaly Detection via Multiscale Contrastive Self-Supervised Learning From Local to Global

引用

IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS 2025年第2期12卷 485-497页

作者： Wang, Xiaofeng Lai, Shuaiming Zhu, Shuailei Chen, Yuntao Lv, Laishui Qi, Yuanyuan China Jiliang Univ Sch Informat Engn Hangzhou 310018 Peoples R China

Graph anomaly detection is a challenging task in graph data mining, aiming to recognize unconventional patterns within a network. Recently, there has been increasing attention on graph anomaly detection based on contrastive learning due to its high adaptability to the sample imbalance problem. However, most existing work typically focuses on the contrast of local views while neglecting global comparison information, leading to suboptimal performance. To address this issue, we introduce a new multiscale contrastive self-supervised learning framework for graph anomaly detection (GADMCLG). Our approach incorporates local-level contrasts involving node-node and node- subgraph contrast, and global-level subgraph-subgraph contrast. The former mines localized abnormal information, while the latter is intended to capture global anomalous patterns. Specifically, our proposed subgraph-subgraph contrast adopts the h-order neighbor subgraph sampling instead of augmented subgraphs through edge perturbation. This sampling strategy ensures a comprehensive observation of the neighborhood surrounding the target node, thereby mitigating the introduction of extraneous noise and providing interpretability for the detected results. Furthermore, we incorporate a subgraph centralization technique to reduce the bias caused by the absolute position of subgraphs in the attribute space, which enhances the model's ability to identify anomalies at different scales. Extensive experimental results on six real-world datasets demonstrate the effectiveness of our method and its superiority compared with state-of-the-art approaches.

关键词： Contrastive learning Contrastive learning graph anomaly detection graph anomaly detection multiscale framework multiscale framework subgraph centralization subgraph centralization subgraph sampling subgraph sampling

来源：评论

学校读者我要写书评

暂无评论

Effectiveness and Efficiency: Label- Aware Hierarchical subgraph Learning for Protein-Protein Interaction

引用

JOURNAL OF MOLECULAR BIOLOGY 2025年第6期437卷 168737页

作者： Zhou, Yuanqing Lin, Haitao Xie, Lianghua Huang, Yufei Wu, Lirong Li, Stan Z. Chen, Wei Zhejiang Univ Coll Biosyst Engn & Food Sci Dept Food Sci & Nutr Hangzhou 310058 Peoples R China Westlake Univ Res Ctr Ind Future AI Lab Hangzhou 310024 Peoples R China

The study of protein-protein interactions (PPIs) holds immense significance in understanding various biological activities, as well as in drug discovery and disease diagnosis. Existing deep learning methods for PPI prediction, including graph neural networks (GNNs), have been widely employed as the solutions, while they often experience a decline in performance in the real world. We claim that the topological shortcut is one of the key problems contributing negatively to the performance, according to our analysis. By modeling the PPIs as a graph with protein as nodes and interactions as edge types, the prevailing models tend to learn the pattern of nodes' degrees rather than intrinsic sequence-structure profiles, leading to the problem termed topological shortcut. The huge data growth of PPI leads to intensive computational costs and challenges computing devices, causing infeasibility in practice. To address the discussed problems, we propose a label-aware hierarchical subgraph learning method (laruGL-PPI) that can effectively infer PPIs while being interpretable. Specifically, we introduced edge-based subgraph sampling to effectively alleviate the problems of topological shortcuts and high computing costs. Besides, the inner-outer connections of PPIs are modeled as a hierarchical graph, together with the dependencies between interaction types constructed by a label graph. Extensive experiments conducted across various scales of PPI data- sets have conclusively demonstrated that the laruGL-PPI method surpasses the most advanced PPI prediction techniques currently available, particularly in the testing of unseen proteins. Also, our model can recognize crucial sites of proteins, such as surface sites for binding and active sites for catalysis. (c) 2024 Elsevier Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： protein-protein interaction multiple graph learning subgraph sampling deep learning

来源：评论

学校读者我要写书评

暂无评论

Measuring and sampling: A metric-guided subgraph learning framework for graph neural network

引用

INTERNATIONAL JOURNAL OF INTELLIGENT SYSTEMS 2022年第10期37卷 7502-7525页

作者： Bai, Jiyang Ren, Yuxiang Zhang, Jiawei Florida State Univ Dept Comp Sci Tallahassee FL 32306 USA Florida State Univ Dept Comp Sci IFM Lab Tallahassee FL 32306 USA Univ Calif Davis Dept Comp Sci IFM Lab Davis CA 95616 USA

Graph neural networks (GNNs) have shown convincing performance in learning powerful node representations that preserve both node attributes and graph structural information. However, many GNNs encounter problems in effectiveness and efficiency when they are designed with a deeper network structure or handle large-sized graphs. Several sampling algorithms have been proposed for improving and accelerating the training of GNNs, yet they ignore understanding the source of GNNs performance gain. The measurement of information within graph data can help the sampling algorithms to keep high-value information while removing redundant information and even noise. In this paper, we propose a Metric-Guided (MeGuide) subgraph learning framework for GNNs. MeGuide employs two novel metrics: Feature Smoothness and Connection Failure Distance to guide the subgraph sampling and mini-batch based training. Feature Smoothness is designed for analyzing the feature of nodes to retain the most valuable information, while Connection Failure Distance can measure the structural information to control the size of subgraphs. We demonstrate the effectiveness and efficiency of MeGuide in training various GNNs on multiple data sets.

关键词： graph neural network subgraph sampling training optimization

来源：评论

学校读者我要写书评

暂无评论

引用

INTELLIGENT DATA ANALYSIS 2023年第6期27卷 1615-1636页

作者： Hou, Linlin Zhang, Haixiang Hou, Qing-Hu Guo, Alan J. X. Wu, Ou Yu, Ting Zhang, Ji Zhejiang Lab Hangzhou Zhejiang Peoples R China Tianjin Univ Ctr Appl Math Tianjin Peoples R China Univ Southern Queensland Darling Hts Australia

Graph Convolutional Network (GCN) is an important method for learning graph representations of nodes. For large-scale graphs, the GCN could meet with the neighborhood expansion phenomenon, which makes the model complexity high and the training time long. An efficient solution is to adopt graph sampling techniques, such as node sampling and random walk sampling. However, the existing sampling methods still suffer from aggregating too many neighbor nodes and ignoring node feature information. Therefore, in this paper, we propose a new subgraph sampling method, namely, Similarity-Aware Random Walk (SARW), for GCN with large-scale graphs. A novel similarity index between two adjacent nodes is proposed, describing the relationship of nodes with their neighbors. Then, we design a sampling probability expression between adjacent nodes using node feature information, degree information, neighbor set information, etc. Moreover, we prove the unbiasedness of the SARW-based GCN model for node representations. The simplified version of SARW (SSARW) has a much smaller variance, which indicates the effectiveness of our subgraph sampling method in large-scale graphs for GCN learning. Experiments on six datasets show our method achieves superior performance over the state-of-the-art graph sampling approaches for the large-scale graph node classification task.

关键词： Similarity-Aware Random Walk subgraph sampling Graph Convolutional Network large-scale graphs random walk

来源：评论

学校读者我要写书评

暂无评论

Inferring Higher-Order Structure Statistics of Large Networks from Sampled Edges

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2019年第1期31卷 61-74页

作者： Wang, Pinghui Qi, Yiyan Lui, John C. S. Towsley, Don Zhao, Junzhou Tao, Jing Xi An Jiao Tong Univ MOE Key Lab Intelligent Networks & Network Secur POB 108828 Xianning West Rd Xian 710049 Shaanxi Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA

Recently exploring locally connected subgraphs (also known as motifs or graphlets) of complex networks attracts a lot of attention. Previous work made the strong assumption that the graph topology of interest is known in advance. In practice, sometimes researchers have to deal with the situation where the graph topology is unknown because it is expensive to collect and store all topological information. Hence, typically what is available to researchers is only a snapshot of the graph, i.e., a subgraph of the graph. Crawling methods such as breadth first sampling can be used to generate the snapshot. However, these methods fail to sample a streaming graph represented as a high speed stream of edges. Therefore, graph mining applications such as network traffic monitoring usually use random edge sampling (i.e., sample each edge with a fixed probability) to collect edges and generate a sampled graph, which we call a "RESampled graph". Clearly, a RESampled graph's motif statistics may be quite different from those of the original graph. To resolve this, we propose a framework Minfer, which takes the given RESampled graph and accurately infers the underlying graph's motif statistics. Experiments using large scale datasets show the accuracy and efficiency of our method.

关键词： Graphlet motif subgraph sampling graph mining

来源：评论

学校读者我要写书评

暂无评论

MOSS-5: A Fast Method of Approximating Counts of 5-Node Graphlets in Large Graphs

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2018年第1期30卷 73-86页

作者： Wang, Pinghui Zhao, Junzhou Zhang, Xiangliang Li, Zhenguo Cheng, Jiefeng Lui, John C. S. Towsley, Don Tao, Jing Guan, Xiaohong Xi An Jiao Tong Univ MOE Key Lab Intelligent Networks & Network Secur Xianning West Rd Xian 710049 Shaanxi Peoples R China Xi An Jiao Tong Univ Shenzhen Res Inst Shenzhen 518057 Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China King Abdullah Univ Sci & Technol Machine Intelligence & Knowledge Engn MINE Lab Thuwal 23955 Saudi Arabia Huawei Noahs Ark Lab Shatin Hong Kong Peoples R China Tencent Cloud Secur Lab Shenzhen 518057 Peoples R China Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA Tsinghua Univ Ctr Intelligent & Networked Syst Tsinghua Natl Lab Informat Sci & Technol Beijing Peoples R China

Counting 3-, 4-, and 5-node graphlets in graphs is important for graph mining applications such as discovering abnormal/evolution patterns in social and biology networks. In addition, it is recently widely used for computing similarities between graphs and graph classification applications such as protein function prediction and malware detection. However, it is challenging to compute these graphlet counts for a large graph or a large set of graphs due to the combinatorial nature of the problem. Despite recent efforts in counting 3-node and 4-node graphlets, little attention has been paid to characterizing 5-node graphlets. In this paper, we develop a computationally efficient sampling method to estimate 5-node graphlet counts. We not only provide a fast sampling method and unbiased estimators of graphlet counts, but also derive simple yet exact formulas for the variances of the estimators which are of great value in practice-the variances can be used to bound the estimates' errors and determine the smallest necessary sampling budget for a desired accuracy. We conduct experiments on a variety of real-world datasets, and the results show that our method is several orders of magnitude faster than the state-of-the-art methods with the same accuracy.

关键词： Graphlet kernel subgraph sampling graph mining

来源：评论

学校读者我要写书评

暂无评论

Efficient and Near-optimal Algorithms for sampling Small Connected subgraphs

引用

ACM TRANSACTIONS ON ALGORITHMS 2023年第3期19卷 1-40页

作者： Bressan, Marco Univ Milan Dipartimento Informat Via Celoria 18 I-20133 Milan Italy

We study the following problem: Given an integer k >= 3 and a simple graph G, sample a connected induced k-vertex subgraph ofG uniformly at random. This is a fundamental graph mining primitive with applications in social network analysis, bioinformatics, and more. Surprisingly, no efficient algorithm is known for uniform sampling;the only somewhat efficient algorithms available yield samples that are only approximately uniform, with running times that are unclear or suboptimal. In this work, we provide: (i) a near-optimal mixing time bound for a well-known random walk technique, (ii) the first efficient algorithm for truly uniform graphlet sampling, and (iii) the first sublinear-time algorithm for e-uniform graphlet sampling.

关键词： subgraph sampling random walks sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：