Comparing structured objects such as graphs is a fundamental operation
involved in many learning tasks. To this end, the Gromov-Wasserstein (GW)
distance, based on Optimal Transport (OT), has proven to be successful in
handling the specific nature of the associated objects. More specifically,
through the nodes connectivity relations, GW operates on graphs, seen as
probability measures over specific spaces. At the core of OT is the idea of
conservation of mass, which imposes a coupling between all the nodes from the
two considered graphs. We argue in this paper that this property can be
detrimental for tasks such as graph dictionary or partition learning, and we
relax it by proposing a new semi-relaxed Gromov-Wasserstein divergence. Aside
from immediate computational benefits, we discuss its properties, and show that
it can lead to an efficient graph dictionary learning algorithm. We empirically
demonstrate its relevance for complex tasks on graphs such as partitioning,
clustering and completion.

本文探讨使用 Gromov-Wasserstein 距离进行图像比较时所涉及的质量损失和计算效率问题，并提出了一种新的模糊 Gromov-Wasserstein 距离，以提高计算效率和准确度，同时在图形字典学习和分区学习等多个领域实现了优异表现。

应用于图上的半松弛 Gromov-Wasserstein 散度

Semi-relaxed Gromov-Wasserstein divergence with applications on graphs

Graph comparison is a fundamental operation in data mining and information
retrieval. Due to the combinatorial nature of graphs, it is hard to balance the
expressiveness of the similarity measure and its scalability. Spectral analysis
provides quintessential tools for studying the multi-scale structure of graphs
and is a well-suited foundation for reasoning about differences between graphs.
However, computing full spectrum of large graphs is computationally
prohibitive; thus, spectral graph comparison methods often rely on rough
approximation techniques with weak error guarantees. In this work, we propose
SLaQ, an efficient and effective approximation technique for computing spectral
distances between graphs with billions of nodes and edges. We derive the
corresponding error bounds and demonstrate that accurate computation is
possible in time linear in the number of graph edges. In a thorough
experimental evaluation, we show that SLaQ outperforms existing methods,
oftentimes by several orders of magnitude in approximation accuracy, and
maintains comparable performance, allowing to compare million-scale graphs in a
matter of minutes on a single machine.

本文提出了一种有效的图谱比较方法 SLaQ，该方法使用谱分析技术计算大规模图结构的相似度，可在线性时间内获取误差较小的结果。实验结果表明 SLaQ 的精度比现有方法提高了数个数量级，且在单机上能够在几分钟内比较百万级别的图。

大规模网络图精确谱距离的近似计算方法 SLaQ

Just SLaQ When You Approximate: Accurate Spectral Distances for  Web-Scale Graphs

Comparison among graphs is ubiquitous in graph analytics. However, it is a
hard task in terms of the expressiveness of the employed similarity measure and
the efficiency of its computation. Ideally, graph comparison should be
invariant to the order of nodes and the sizes of compared graphs, adaptive to
the scale of graph patterns, and scalable. Unfortunately, these properties have
not been addressed together. Graph comparisons still rely on direct approaches,
graph kernels, or representation-based methods, which are all inefficient and
impractical for large graph collections.
In this paper, we propose the Network Laplacian Spectral Descriptor (NetLSD):
the first, to our knowledge, permutation- and size-invariant, scale-adaptive,
and efficiently computable graph representation method that allows for
straightforward comparisons of large graphs. NetLSD extracts a compact
signature that inherits the formal properties of the Laplacian spectrum,
specifically its heat or wave kernel; thus, it hears the shape of a graph. Our
evaluation on a variety of real-world graphs demonstrates that it outperforms
previous works in both expressiveness and efficiency.

本文提出了 Network Laplacian Spectral Descriptor（NetLSD）方法，可以实现对大型图的快速比较，该方法是目前为止唯一一种既具有置换和尺寸等变性，同时又可扩展和高效计算的图形表示方法，并且具有比以往方法更好的表达性和效率。