Graph Substructure Learning, Mining and Explanation

<p dir="ltr">Graph substructures which could be single nodes, communities and other subgraphs derived from the node-link structured graphs, represent functional patterns in practical applications. However, traditional graph mining methods often rely solely on learning features on nodes and complicated relationships but neglect functional substructures, which brings significant challenges. Firstly, graph-structured data exhibit domain-specific distributions that align with the characteristics of target applications. Off-the-shelf graph-based methods which excel in general tasks (e.g., classification and clustering), often struggle to consistently handle the mining demands posed by data that deviates from the common distributions observed in generic datasets. Secondly, in endeavours aimed at enhancing mining performance in the social sciences, there exists a lack of exploration regarding graph substructure patterns that characterise the social behaviours of objects. Lastly, specific graph substructures acting as functional units, hold significant potential to provide underlying explanations for the decision-making of deep models on graph-structured data. In response to these challenges, this thesis contributes to advancing the exploration of graph substructures in terms of learning, mining and explanation, with the aim of enabling the effective and reliable deployment of graph mining approaches. The research can be reviewed in three parts: (1) Deep anomalous node detection empowered with data augmentation. A simple and effective data augmentation scheme is put forward to work with graph neural networks (GNNs) for anomalous node detection. (2) Graph-based e-commerce risky community detection. We devise a platform to explore communities of potential fraudsters based on cohesive substructures, serving the identification of e-commerce fraud gangs. (3) Graph substructures as explanations for GNNs. We introduce a unified subgraph dependency learning framework, which presents an efficient and effective self-explainable design to capture subgraphs significant to predictions within the context of global explainability of GNNs.</p>