The graph classification problem has been widely studied; however, achieving
an interpretable model with high predictive performance remains a challenging
issue. This paper proposes an interpretable classification algorithm for
attributed graph data, called LAGRA (Learning Attributed GRAphlets). LAGRA
learns importance weights for small attributed subgraphs, called attributed
graphlets (AGs), while simultaneously optimizing their attribute vectors. This
enables us to obtain a combination of subgraph structures and their attribute
vectors that strongly contribute to discriminating different classes. A
significant characteristics of LAGRA is that all the subgraph structures in the
training dataset can be considered as a candidate structures of AGs. This
approach can explore all the potentially important subgraphs exhaustively, but
obviously, a naive implementation can require a large amount of computations.
To mitigate this issue, we propose an efficient pruning strategy by combining
the proximal gradient descent and a graph mining tree search. Our pruning
strategy can ensure that the quality of the solution is maintained compared to
the result without pruning. We empirically demonstrate that LAGRA has superior
or comparable prediction performance to the standard existing algorithms
including graph neural networks, while using only a small number of AGs in an
interpretable manner.

通过结合近端梯度下降和图挖掘树搜索，本文提出了一种针对属性图数据的可解释分类算法 LAGRA（Learning Attributed GRAphlets），能够同时学习重要性权重和属性向量，从而获得对于区分不同类别有很大贡献的子图结构和属性向量的组合，同时将所有训练数据集中的子图结构视为候选的 AG（attributed graphlets）的结构，通过剪枝策略来提高计算效率并保持解决方案的质量，实验证明 LAGRA 在可解释的方式下仅使用少量 AGs 就能具有优秀的预测性能。