While most network embedding techniques model the proximity between nodes in
a network, recently there has been significant interest in structural
embeddings that are based on node equivalences, a notion rooted in sociology:
equivalences or positions are collections of nodes that have similar
roles--i.e., similar functions, ties or interactions with nodes in other
positions--irrespective of their distance or reachability in the network.
Unlike the proximity-based methods that are rigorously evaluated in the
literature, the evaluation of structural embeddings is less mature. It relies
on small synthetic or real networks with labels that are not perfectly defined,
and its connection to sociological equivalences has hitherto been vague and
tenuous. With new node embedding methods being developed at a breakneck pace,
proper evaluation and systematic characterization of existing approaches will
be essential to progress. To fill in this gap, we set out to understand what
types of equivalences structural embeddings capture. We are the first to
contribute rigorous intrinsic and extrinsic evaluation methodology for
structural embeddings, along with carefully-designed, diverse datasets of
varying sizes. We observe a number of different evaluation variables that can
lead to different results (e.g., choice of similarity measure, classifier,
label definitions). We find that degree distributions within nodes' local
neighborhoods can lead to simple yet effective baselines in their own right and
guide the future development of structural embedding. We hope that our findings
can influence the design of further node embedding methods and also pave the
way for more comprehensive and fair evaluation of structural embedding methods.

本研究探讨基于节点等价性的结构嵌入技术，并提供了严谨的内在和外在评估方法，发现节点邻域度数分布可以成为简单却有效的基准，并希望这些发现能够影响节点嵌入方法的设计并促进更全面和公正地评估结构嵌入方法。

探究和评估结构节点嵌入

Towards Understanding and Evaluating Structural Node Embeddings

Deciding the equivalence of SQL queries is a fundamental problem in data
management. As prior work has mainly focused on studying the theoretical
limitations of the problem, very few implementations for checking such
equivalences exist. In this paper, we present a new formalism and
implementation for reasoning about the equivalences of SQL queries. Our
formalism, U-semiring, extends SQL's semiring semantics with unbounded
summation and duplicate elimination. U-semiring is defined using only very few
axioms and can thus be easily implemented using proof assistants such as Coq
for automated query reasoning. Yet, they are sufficient enough to enable us
reason about sophisticated SQL queries that are evaluated over bags and sets,
along with various integrity constraints. To evaluate the effectiveness of
U-semiring, we have used it to formally verify 39 query rewrite rules from both
classical data management research papers and real-world SQL engines, where
many of them have never been proven correct before.

本文提出了一种新的形式主义和基于 U-semiring 的实现，扩展了 SQL 的半环语义，并利用 U-semiring 对 SQL 查询的等价性进行推理，该方法能够应对不同的完整约束和集合；我们还对 39 个查询重写规则进行了正式验证。