Graph Data Mining: Algorithm, Security and Application (Big Data Management)

Graph data is powerful, thanks to its ability to model arbitrary relationship between objects and is encountered in a range of real-world applications in fields such as bioinformatics, traffic network, scientific collaboration, world wide web and social networks. Graph data mining is used to discover useful information and knowledge from graph data. The complications of nodes, links and the semi-structure form present challenges in terms of the computation tasks, e.g., node classification, link prediction, and graph classification. In this context, various advanced techniques, including graph embedding and graph neural networks, have recently been proposed to improve the performance of graph data mining. This book provides a state-of-the-art review of graph data mining methods. It addresses a current hot topic – the security of graph data mining – and proposes a series of detection methods to identify adversarial samples in graph data. In addition, it introduces readers to graph augmentation and subgraph networks to further enhance the models, i.e., improve their accuracy and robustness. Lastly, the book describes the applications of these advanced techniques in various scenarios, such as traffic networks, social and technical networks, and blockchains. Preface 6 References 11 Acknowledgment 14 Contents 15 1 Information Source Estimation with Multi-Channel Graph Neural Network 17 1.1 Introduction 17 1.2 Related Work 21 1.2.1 Information Diffusion Modeling 21 1.2.2 Information Source Detection 21 1.2.3 Graph Neural Network 23 1.3 Preliminaries 24 1.3.1 Problem Definition 24 1.4 Multi-Channel Graph Neural Network 26 1.4.1 Feature Indices of Input 26 1.4.1.1 Structural Features 27 1.4.1.2 Prior Knowledge Features 28 1.4.2 Graph Convolutional Networks 30 1.4.3 Architecture of MCGNN 30 1.4.4 Loss Function 31 1.5 Experiment 33 1.5.1 Datasets and Experimental Setup 33 1.5.2 Baselines and Evaluation Metrics 33 1.5.3 Results on the Synthetic Networks 35 1.5.4 Results on the Real-World Networks 37 1.6 Conclusion 41 References 41 2 Link Prediction Based on Hyper-Substructure Network 44 2.1 Introduction 44 2.2 Existing Link Prediction Methods 46 2.2.1 Heuristic Methods 46 2.2.2 Embedding-Based Methods 47 2.2.3 Deep Learning-Based Models 49 2.3 Methodology 49 2.3.1 Problem Formulation 50 2.3.2 Neighborhood Normalization 50 2.3.3 HSN Construction 51 2.3.4 HELP 53 2.4 Experiment 55 2.4.1 Datasets 55 2.4.2 Link Prediction Methods for Comparison 55 2.4.3 Evaluation Metrics 56 2.4.4 Experimental Settings 56 2.4.5 Link Prediction Results 57 2.4.6 Parameter Sensitivity 58 2.5 Conclusion 61 References 61 3 Broad Learning Based on Subgraph Networks for Graph Classification 64 3.1 Introduction 65 3.2 Related Work 66 3.2.1 Subgraph Networks 66 3.2.2 Network Representation 67 3.2.3 Broad Learning System 67 3.3 Subgraph Networks 68 3.3.1 First-Order SGN 69 3.3.2 Second-Order SGN 70 3.4 Sampling Subgraph Networks 72 3.4.1 Sampling Strategies 72 3.4.1.1 Biased Walk (BW) 72 3.4.1.2 Spanning Tree (ST) 73 3.4.1.3 Forest Fire (FF) 74 3.4.2 Construction of S2GN 75 3.5 BLS Classifier Based on S2GN 75 3.5.1 BLS Classifier 75 3.5.2 Classification Framework 77 3.6 Experiment 79 3.6.1 Graph Classification 79 3.6.2 Datasets 79 3.6.3 Network Representation 80 3.6.4 SGN for Graph Classification 81 3.6.5 S2GN for Graph Classification 82 3.7 Computational Complexity 83 3.8 Conclusion 84 References 85 4 Subgraph Augmentation with Application to Graph Mining 87 4.1 Introduction 88 4.2 Related Work 89 4.2.1 Graph Classification 89 4.2.1.1 Graph Kernel Methods 89 4.2.1.2 Embedding Methods 89 4.2.1.3 Deep Learning Methods 89 4.2.2 Data Augmentation in Graph Learning 90 4.3 The Model Evolution Framework for Graph Classification 90 4.3.1 Problem Formulation 90 4.3.2 Subgraph Augmentation 91 4.3.2.1 Random Mapping 92 4.3.2.2 Motif-Similarity Mapping 92 4.3.3 Data Filtration 95 4.3.4 Model Evolution Framework 95 4.4 Application of Subgraph Augmentation 96 4.4.1 Graph Classification 97 4.4.1.1 Experimental Setting 97 4.4.2 Link Prediction 98 4.4.2.1 Subgraph Extraction 98 4.4.2.2 Experimental Setting 99 4.4.3 Node Classification 99 4.4.3.1 Subgraph Extraction 100 4.4.3.2 Experimental Setting 100 4.4.4 Experimental Results 100 4.5 Conclusion 102 References 103 5 Adversarial Attacks on Graphs: How to Hide Your Structural Information 106 5.1 Background 107 5.2 Adversarial Attack 109 5.2.1 Problem Definition 109 5.2.2 Taxonomies of Attacks 109 5.3 Attack Strategy 111 5.3.1 Node Classification 111 5.3.1.1 NETTACK 112 5.3.1.2 Meta Attack 114 5.3.1.3 Experiment of Results 116 5.3.2 Link Prediction 117 5.3.2.1 Heuristic Attack 118 5.3.2.2 Gradient-Based Attack 119 5.3.2.3 Experiment of Results 121 5.3.3 Graph Classification 122 5.3.3.1 Hierarchical Reinforcement Learning Attack 122 5.3.3.2 Experimental Result 125 5.3.4 Community Detection 126 5.3.4.1 GA-Based Q-Attack 126 5.3.4.2 Experiment Result 128 5.4 Conclusion 129 References 131 6 Adversarial Defenses on Graphs: Towards Increasing the Robustness of Algorithms 134 6.1 Introduction 134 6.2 Adversarial Training 136 6.2.1 Graph Adversarial Training 136 6.2.2 SAT 139 6.3 Graph Purification 142 6.3.1 GCN-Jaccard 142 6.3.2 GCN-SVD 144 6.4 Robustness Certification 146 6.4.1 Certifying Robustness for Graph Structure Perturbations 146 6.4.2 Certifying Robustness for Node Attributes Perturbations 147 6.4.3 Certifiable Robustness in Community Detection 149 6.5 Structure Based Defense 151 6.5.1 Penalized Aggregation GNN 151 6.5.2 Robust Graph Convolutional Network 153 6.6 Adversarial Detection 155 6.6.1 Adversarial Detection on Node Classification 155 6.6.2 Adversarial Detection on Graph Classification 156 6.6.2.1 SGN Based Adversarial Detection 157 6.6.2.2 Joint Adversarial Detection 157 6.7 Summary of Defenses 158 6.8 Experiment and Analyze 158 6.8.1 Adversarial Training 158 6.8.2 Adversarial Detection 162 6.9 Conclusion 165 References 165 7 Understanding Ethereum Transactions via Network Approach 168 7.1 Introduction 169 7.2 Ethereum Transaction Dataset 170 7.3 Graph Embedding Techniques 172 7.3.1 Factorization Based Methods 173 7.3.2 Random Walk Based Methods 173 7.3.3 Deep Learning Based Methods 174 7.3.4 Other Methods 174 7.4 The Proposed Method 175 7.4.1 Basic Definition 175 7.4.2 Temporal Biased Walk 177 7.4.3 Learning Temporal Graph Embeddings 179 7.5 Experiment 181 7.5.1 Node Classification 181 7.5.1.1 Evaluation Metrics 182 7.5.1.2 Experimental Results 182 7.5.2 Link Prediction 183 7.5.2.1 Evaluation Metrics 183 7.5.2.2 Experimental Results 184 7.6 Conclusion 186 7.7 Appendix 187 7.7.1 Similarity Indices 187 References 188 8 Find Your Meal Pal: A Case Study on Yelp Network 190 8.1 Introduction 190 8.2 Data Description and Preprocessing 192 8.3 Link Prediction Methods 194 8.3.1 Similarity Indices Assembly 194 8.3.2 Variational Graph Auto-Encoder 195 8.4 Experiments 196 8.5 Experiment Setup 196 8.5.1 Friends Recommendation 196 8.5.2 Co-foraging Prediction 198 8.6 Conclusion 200 References 200 9 Graph Convolutional Recurrent Neural Networks: A Deep Learning Framework for Traffic Prediction 202 9.1 Background 202 9.2 Related Work 204 9.2.1 Graph Analysis 204 9.2.2 Traffic State Prediction 204 9.3 Model 205 9.3.1 Graph Convolutional Network 205 9.3.2 Long Short-Term Memory 208 9.3.3 Graph Convolutional Recurrent Neural Network 210 9.4 Experiment 211 9.4.1 Dataset 211 9.4.2 Baselines 212 9.4.3 Evaluation 212 9.4.4 Evaluation 213 9.4.5 Results of Experiments and Analyses 213 9.5 Conclusion 214 References 216 10 Time Series Classification Based on Complex Network 218 10.1 Introduction 218 10.2 Related Work 220 10.2.1 Time Series Classification 220 10.2.2 Mapping Methods 221 10.2.3 Graph Classification 222 10.3 Methods 223 10.3.1 Circular Limited Penetrable Visibility Graph 223 10.3.1.1 Circle System Equation 223 10.3.1.2 Graph Construction through CLPVG 225 10.3.1.3 Subgraph Network 226 10.3.2 Automatic Visibility Graph based on GNN 226 10.3.2.1 The Overall Framework 227 10.3.2.2 Feature Extraction 227 10.3.2.3 Feature Matrix of Graph 228 10.3.2.4 Classification of Graphs 229 10.3.3 Comparison with LPVG 229 10.4 Experiments 230 10.4.1 Datasets 230 10.4.2 The Experimental Settings 231 10.4.3 The Experimental Results 232 10.5 Conclusion 233 References 234 11 Exploring the Controlled Experiment by Social Bots 236 11.1 Introduction 236 11.2 Definition of Social Bots 237 11.3 Application and Influence of Social Bots 238 11.3.1 Application 238 11.3.2 Influence 239 11.4 Development Technology of Social Bots 240 11.4.1 Internet Access Technology 241 11.4.1.1 PC Side 241 11.4.1.2 Browser-based Access 241 11.4.1.3 Mobile 242 11.4.2 Artificial Intelligence Foundation 242 11.4.3 Network Science Theory 242 11.5 Social Bots Detection 242 11.5.1 Graph-based Detection Method 243 11.5.2 Feature-based Detection Method 244 11.5.3 Crowdsourcing Detection Method 245 11.5.4 Mixed Use of Multiple Ways 245 11.6 Social Bots and Social Network Control Experiment 245 11.6.1 Online Social Network Controlled Experiment 247 11.6.2 Application of Social Bots in Controlled Experiment 248 11.6.3 Problems in Controlled Experiments by Social Bots 254 11.6.3.1 High Technical Threshold 254 11.6.3.2 Legal and Moral Issues 254 11.7 Conclusion 254 References 255