Inspired by the success of generative adversarial networks (GANs) in image domains, we introduce a novel hierarchical architecture for learning characteristic topological features from a single arbitrary input graph via GANs. The hierarchical architecture consisting of multiple GANs preserves both local and global topological features, and automatically partitions the input graph into representative stages for feature learning. The stages facilitate reconstruction and can be used as indicators of the importance of the associated topological structures. Experiments show that our method produces subgraphs retaining a wide range of topological features, even in early reconstruction stages. This paper contains original research on combining the use of GANs and graph topological analysis. Graphs have great versatility, able to represent complex systems with diverse relationships between objects and data. With the rise of social networking, and the importance of relational properties to the "big data" phenomenon, it has become increasingly important to develop ways to automatically identify key structures present in graph data. Identification of such structures is crucial in understanding how a social network forms, or in making predictions about future network behavior. To this end, a large number of graph analysis methods have been proposed to analyze network topology at the node BID57 , community BID41 BID55 , and global levels BID64 .Each level of analysis is greatly influenced by network topology, and thus far algorithms cannot be adapted to work effectively for arbitrary network structures. Modularity-based community detection BID65 works well for networks with separate clusters, whereas edge-based methods BID37 are suited to dense networks. Similarly, when performing graph sampling, Random Walk (RW) is suitable for sampling paths BID51 , whereas Forrest Fire (FF) is useful for sampling clusters BID52 . When it comes to graph generation, Watts-Strogatz (WS) graph models BID62 can generate graphs with small world features, whereas Barabsi-Albert (BA) graph models BID31 simulate super hubs and regular nodes according to the scale-free features of the network.However, real-world networks typically have multiple topological features. Considering real-world networks also introduces another issue that traditional graph analysis methods struggle with; having a mere single instance of a graph (e.g. the transaction graph for a particular bank), making it difficult to identify the key topological properties in the first place. In particular, we are interested in both "local topological features" (such as the presence of subgraph structures like triangles) and "global topological features" such as degree distribution.Instead of directly analyzing the entire topology of a graph, GTI first divides the graph into several hierarchical layers. A hierarchical view of a graph can split the graph by local and global topological features, leading to a better understanding of the graph BID63 . As different layers have different topological features, GTI uses separate GANs to learn each layer and the associated features. By leveraging GANs renowned feature identification BID42 on each layer, GTI has the ability to automatically capture arbitrary topological features from a single input graph. Figure 1 demonstrates how GTI can learn to reproduce an input graph where a single GAN cannot.In addition to learning topological features from the input graph, the GTI method defines a reconstruction process for reproducing the original graph via a series of reconstruction stages (the number Figure 1 : How GTI recovers the original graph while naive GAN methods do not: The DCGAN output looks like a complete graph, whereas GTI can capture the super-hub structure of node 3 and node 2.of which is automatically learned during training). As stages are ranked in order of their contribution to the full topology of the original graph, early stages can be used as an indicator of the most important topological features. Our focus in this initial work is on the method itself and demonstrating our ability to learn these important features quickly (via demonstrating the retention of identifiable structures and comparisons to graph sampling methods). This paper leveraged the success of GANs in (unsupervised) image generation to tackle a fundamental challenge in graph topology analysis: a model-agnostic approach for learning graph topological features. By using a GAN for each hierarchical layer of the graph, our method allowed us to reconstruct diverse input graphs very well, as well as preserving both local and global topological features when generating similar (but smaller) graphs. In addition, our method identifies important features through the definition of the reconstruction stages. A clear direction of future research is in extending the model-agnostic approach to allow the input graph to be directed and weighted, and with edge attributes.
A GAN based method to learn important topological features of an arbitrary input graph.
{"src": "scitldr-AIC_train", "paper_id": "BJcAWaeCW"}