Graph Summarization
In this line of work, we develop algorithms for graph summarization, the problem of producing smaller graph representations of an input graph dataset, in such a way that the smaller compressed graphs capture relevant structural information for downstream tasks. Towards achieving this ultimate objective, our goals are (1) to give a natural formalization of supervised graph summarization and explore limitations on its computational tractability; (2) adapt the existing graph summarization (including optimal transport (OT)) framework to incorporate information about class labels; and (3) provide theoretical and empirical intuition/analysis about the strengths and limitations of the recent approaches for supervised graph summarization.
Graph Neural Networks (GNNs) have gained significant attention for their exceptional performance in graph learning and node classification tasks. However, large-scale graph learning via GNNs evolves expensive computational complexity in both the training and testing phases. Subgraph learning tackles computational efficiency challenges while capturing the information through the underlying graph neighborhoods with respect to node labels. Despite the efficiency advantage of subgraphs, their performance is vulnerable to adversarial attacks through susceptible nodes.
In this research, we tackle graph summarization challenge with focus on subgraph robustness goals.