Robust Data Mining of Large-Scale Attributed Graphs

• Applicant: Professor Dr. Stephan Günnemann
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2015 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 267560157

• Final Report Year: 2022

Final Report Abstract

The ambition of the Emmy Noether project was to advance our understanding about robustness of graphbased data mining / machine learning techniques. With the increasing use of graph machine learning in various application domains, the need of reliable techniques becomes ever more important. In the scope of the project, we advanced the field in three different directions: (1) We proposed different approaches which are able to perturb/corrupt graphs so that vulnerabilities in the used machine learning technique become apparent. Among others, we investigated the robustness of graph neural networks and graph embeddings. All studies have shown that graph-based learning techniques are highly susceptible to corruptions in the data and that results have to be considered carefully. (2) We developed techniques improving robustness of the models. The advancements proposed range from more robust clustering techniques, over advanced training procedures, up to improved graph neural network architectures. In various experimental studies, we have shown the benefit of using these robust models over the non-robust baselines. (3) We studied procedures for certifying robustness of graph-based models, i.e. providing mathematical guarantees about the stability of a model’s outcomes. The certificates cover white-box certificates that exploit the specificities of certain classes of approaches, e.g. graph convolutional networks, and black-box certificates which are general applicable and model-agnostic. Hand in hand with these main directions, we investigated various approaches for scaling up the proposed approaches and graph-learning techniques in general taking into account, e.g., the sparsity of data or considering large-scale / distributed learning settings.

Publications

• Robust Spectral Clustering for Noisy Data: Modeling Sparse Corruptions Improves Latent Embeddings. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2017
  Aleksandar Bojchevski, Yves Matkovic, Stephan Günnemann
  (See online at https://doi.org/10.1145/3097983.3098156)
• Adversarial Attacks on Neural Networks for Graph Data. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2018 [Best Research Paper Award]
  Daniel Zügner, Amir Akbarnejad, Stephan Günnemann
  (See online at https://doi.org/10.1145/3219819.3220078)
• Bayesian Robust Attributed Graph Clustering: Joint Learning of Partial Anomalies and Group Structure. AAAI Conference on Artificial Intelligence, 2018
  Aleksandar Bojchevski, Stephan Günnemann
  (See online at https://doi.org/10.1609/aaai.v32i1.11642)
• Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking. International Conference on Learning Representations (ICLR), 2018
  Aleksandar Bojchevski, Stephan Günnemann
  (See online at https://doi.org/10.48550/arXiv.1707.03815)
• Adversarial Attacks on Node Embeddings via Graph Poisoning. International Conference on Machine Learning (ICML), 2019
  Aleksandar Bojchevski, Stephan Günnemann
  (See online at https://doi.org/10.48550/arXiv.1809.01093)
• Certifiable Robustness and Robust Training for Graph Convolutional Networks. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2019
  Daniel Zügner, Stephan Günnemann
  (See online at https://doi.org/10.48550/arXiv.1906.12269)
• Certifiable Robustness to Graph Perturbations. Neural Information Processing Systems (NeurIPS), 2019
  Aleksandar Bojchevski, Stephan Günnemann
  (See online at https://doi.org/10.48550/arXiv.1910.14356)
• Certifiable Robustness of Graph Convolutional Networks under Structure Perturbations. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2020
  Daniel Zügner, Stephan Günnemann
  (See online at https://doi.org/10.1145/3394486.3403217)
• Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More. International Conference on Machine Learning (ICML), 2020
  Aleksandar Bojchevski, Johannes Gasteiger, Stephan Günnemann
  (See online at https://doi.org/10.48550/arXiv.2008.12952)
• Reliable Graph Neural Networks via Robust Aggregation. Neural Information Processing Systems (NeurIPS), 2020
  Simon Geisler, Daniel Zügner, Stephan Günnemann
  (See online at https://doi.org/10.48550/arXiv.2010.15651)