N2N: Network Derivative Mining
N2N: Network Derivative Mining
复制标题
DOI：
10.1145/3357384.3357910
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Jian Kang;Hanghang Tong
中科院分区：
文献类型：
--
作者：
Jian Kang;Hanghang Tong
网络挖掘在许多高影响力的应用领域中起着关键作用，包括信息检索，医疗保健，社交网络分析，安全和推荐系统。最先进的网络挖掘算法提供了丰富的复杂的，其中许多已被广泛采用，在现实世界中的上级经验性能。尽管如此，他们往往缺乏有效和高效的方法来表征一个给定的挖掘任务的结果如何与底层网络结构。本文介绍了网络衍生挖掘问题。给定输入网络和特定的挖掘算法，网络导数挖掘找到一个导数网络，其边度量输入网络的相应边对挖掘结果的影响。我们设想，网络衍生挖掘可能是有益的，在各种情况下，从可解释的网络挖掘，对抗性网络挖掘，网络结构的敏感性分析，主动学习，边信息学习，网络上的反事实学习。我们从优化的角度提出了一个通用的网络衍生挖掘框架，并提供了三个经典的网络挖掘任务，包括排名，聚类和矩阵完成各种实例。对于每个挖掘任务，我们开发了有效的算法，用于构建基于影响函数分析的衍生网络，并进行了多次优化，以确保在时间和空间上的线性复杂度。在真实数据集上进行的大量实验验证了所提出的框架和算法的有效性。
Network mining plays a pivotal role in many high-impact application domains, including information retrieval, healthcare, social network analysis, security and recommender systems. State-of-the-art offers a wealth of sophisticated network mining algorithms, many of which have been widely adopted in real-world with superior empirical performance. Nonetheless, they often lack effective and efficient ways to characterize how the results of a given mining task relate to the underlying network structure. In this paper, we introduce network derivative mining problem. Given the input network and a specific mining algorithm, network derivative mining finds a derivative network whose edges measure the influence of the corresponding edges of the input network on the mining results. We envision that network derivative mining could be beneficial in a variety of scenarios, ranging from explainable network mining, adversarial network mining, sensitivity analysis on network structure, active learning, learning with side information to counterfactual learning on networks. We propose a generic framework for network derivative mining from the optimization perspective and provide various instantiations for three classic network mining tasks, including ranking, clustering, and matrix completion. For each mining task, we develop effective algorithm for constructing the derivative network based on influence function analysis, with numerous optimizations to ensure a linear complexity in both time and space. Extensive experimental evaluation on real-world datasets demonstrates the efficacy of the proposed framework and algorithms.