Front-door adjustment is a classic technique to estimate causal effects from
a specified directed acyclic graph (DAG) and observed data. The advantage of
this approach is that it uses observed mediators to identify causal effects,
which is possible even in the presence of unobserved confounding. While the
statistical properties of the front-door estimation are quite well understood,
its algorithmic aspects remained unexplored for a long time. Recently, Jeong,
Tian, and Barenboim [NeurIPS 2022] have presented the first polynomial-time
algorithm for finding sets satisfying the front-door criterion in a given DAG,
with an $O(n^3(n+m))$ run time, where $n$ denotes the number of variables and
$m$ the number of edges of the graph. In our work, we give the first
linear-time, i.e. $O(n+m)$, algorithm for this task, which thus reaches the
asymptotically optimal time complexity, as the size of the input is
$\Omega(n+m)$. We also provide an algorithm to enumerate all front-door
adjustment sets in a given DAG with delay $O(n(n + m))$. These results improve
the algorithms by Jeong et al. [2022] for the two tasks by a factor of $n^3$,
respectively.

本文提出了一种基于有向无环图 (DAG) 的前门调整线性时间算法，可在 O (n+m) 的时间内发现满足前门准则的集合，因此达到渐进最优时间复杂度，并提供了一个算法以 O (n (n+m)) 的延迟列出给定 DAG 中所有前门调整集。

线性时间内找到前门调整集

Finding Front-Door Adjustment Sets in Linear Time

Multiview clustering has been extensively studied to take advantage of
multi-source information to improve the clustering performance. In general,
most of the existing works typically compute an n * n affinity graph by some
similarity/distance metrics (e.g. the Euclidean distance) or learned
representations, and explore the pairwise correlations across views. But
unfortunately, a quadratic or even cubic complexity is often needed, bringing
about difficulty in clustering largescale datasets. Some efforts have been made
recently to capture data distribution in multiple views by selecting view-wise
anchor representations with k-means, or by direct matrix factorization on the
original observations. Despite the significant success, few of them have
considered the view-insufficiency issue, implicitly holding the assumption that
each individual view is sufficient to recover the cluster structure. Moreover,
the latent integral space as well as the shared cluster structure from multiple
insufficient views is not able to be simultaneously discovered. In view of
this, we propose an Adaptively-weighted Integral Space for Fast Multiview
Clustering (AIMC) with nearly linear complexity. Specifically, view generation
models are designed to reconstruct the view observations from the latent
integral space with diverse adaptive contributions. Meanwhile, a centroid
representation with orthogonality constraint and cluster partition are
seamlessly constructed to approximate the latent integral space. An alternate
minimizing algorithm is developed to solve the optimization problem, which is
proved to have linear time complexity w.r.t. the sample size. Extensive
experiments conducted on several realworld datasets confirm the superiority of
the proposed AIMC method compared with the state-of-the-art methods.

提出了一种自适应加权积分空间 (AIMC) 方法，用于快速多视图聚类，该方法具有近乎线性时间复杂度，通过视图生成模型和质心表示构造近似的潜在积分空间和聚类划分，通过多个视图发现了潜在整体空间和共享聚类结构，通过实验验证了该方法的卓越性能。

自适应加权积分空间用于快速多视角聚类

Adaptively-weighted Integral Space for Fast Multiview Clustering

K-means is undoubtedly the most widely used partitional clustering algorithm.
Unfortunately, due to its gradient descent nature, this algorithm is highly
sensitive to the initial placement of the cluster centers. Numerous
initialization methods have been proposed to address this problem. In this
paper, we first present an overview of these methods with an emphasis on their
computational efficiency. We then compare eight commonly used linear time
complexity initialization methods on a large and diverse collection of data
sets using various performance criteria. Finally, we analyze the experimental
results using non-parametric statistical tests and provide recommendations for
practitioners. We demonstrate that popular initialization methods often perform
poorly and that there are in fact strong alternatives to these methods.

本研究探讨了 K-means 算法及其初始化方法在聚类方面的应用，比较了 8 种常用线性时间复杂度的初始化方法，并使用各种性能指标对各种数据集进行了测试和分析， 结论表明，当前通用的初始化方法表现不佳，并且有更好的替代方案。