检索结果-内蒙古大学图书馆

RECOVERING A HIDDEN COMMUNITY BEYOND THE KESTEN-STIGUM THRESHOLD IN O(|E| log* |V|) TIME

JOURNAL OF APPLIED PROBABILITY 2018年第2期55卷 325-352页

作者： Hajek, Bruce Wu, Yihong Xu, Jiaming Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA Yale Univ Dept Stat & Data Sci New Haven CT 06511 USA Purdue Univ Krannert Sch Management W Lafayette IN 47907 USA

Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on weak recovery of the community based on the graph G, with o(K) misclassified vertices on average, in the sublinear regime n(1-o(1)) <= K <= o(n). A critical parameter is the effective signal-to-noise ratio lambda = K-2(p - q)(2)/ ((n - K) q), with lambda = 1 corresponding to the Kesten-Stigum threshold. We show that a belief propagation (BP) algorithm achieves weak recovery if lambda > 1/e, beyond the Kesten-Stigum threshold by a factor of 1/e. The BP algorithm only needs to run for log* n + O(1) iterations, with the total time complexity O(vertical bar E vertical bar log* n), where log* n is the iterated logarithm of n. Conversely, if lambda <= 1/e, no local algorithm can asymptotically outperform trivial random guessing. Furthermore, a linear message-passing algorithm that corresponds to applying a power iteration to the nonbacktracking matrix of the graph is shown to attain weak recovery if and only if lambda > 1. In addition, the BP algorithm can be combined with a linear-time voting procedure to achieve the information limit of exact recovery (correctly classify all vertices with high probability) for all K >= (n/ log n)( rho(BP) + o(1)), where rho(BP) is a function of p/q.

关键词： Hidden community belief propagation message passing spectral algorithms high-dimensional statistics

来源：评论

学校读者我要写书评

暂无评论

A family of tractable graph metrics

引用

APPLIED NETWORK SCIENCE 2019年第1期4卷 1页

作者： Bento, Jose Ioannidis, Stratis Boston Coll Dept Comp Sci St Marys Hall2nd Floor Chestnut Hill MA 02467 USA Northeastern Univ Dept Elect & Comp Engn 360 Huntington Ave Boston MA 02115 USA

Important data mining problems such as nearest-neighbor search and clustering admit theoretical guarantees when restricted to objects embedded in a metric space. Graphs are ubiquitous, and clustering and classification over graphs arise in diverse areas, including, e.g., image processing and social networks. Unfortunately, popular distance scores used in these applications, that scale over large graphs, are not metrics and thus come with no guarantees. Classic graph distances such as, e.g., the chemical distance and the Chartrand-Kubiki-Shultz distance are arguably natural and intuitive, and are indeed also metrics, but they are intractable: as such, their computation does not scale to large graphs. We define a broad family of graph distances, that includes both the chemical and the Chartrand-Kubiki-Shultz distances, and prove that these are all metrics. Crucially, we show that our family includes metrics that are tractable. Moreover, we extend these distances by incorporating auxiliary node attributes, which is important in practice, while maintaining both the metric property and tractability.

关键词： Metric spaces Graph distances Graph matching Graph isomorphism Convex optimization spectral algorithms

来源：评论

学校读者我要写书评

暂无评论

First-principles multiway spectral partitioning of graphs

引用

JOURNAL OF COMPLEX NETWORKS 2014年第2期2卷 121-140页

作者： Riolo, Maria A. Newman, M. E. J. Univ Michigan Dept Math Ann Arbor MI 48109 USA Univ Michigan Ctr Study Complex Syst Ann Arbor MI 48109 USA Univ Michigan Dept Phys Ann Arbor MI 48109 USA

We consider the minimum-cut partitioning of a graph into more than two parts using spectral methods. While there exist well-established spectral algorithms for this problem that give good results, they have traditionally not been well motivated. Rather than being derived from first principles by minimizing graph cuts, they are typically presented without direct derivation and then proved after the fact to work. In this paper, we take a contrasting approach in which we start with a matrix formulation of the minimum cut problem and then show, via a relaxed optimization, how it can be mapped onto a spectral embedding defined by the leading eigenvectors of the graph Laplacian. The end result is an algorithm that is similar in spirit to, though different in detail from, previous spectral partitioning approaches.

关键词： graph partitioning graph spectra spectral algorithms networks

来源：评论

学校读者我要写书评

暂无评论

Synchronization over Z(2) and community detection in signed multiplex networks with constraints

引用

JOURNAL OF COMPLEX NETWORKS 2015年第3期3卷 469-506页

作者： Cucuringu, Mihai Princeton Univ PACM Fine HallWashington Rd Princeton NJ 08544 USA Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA

Finding group elements from noisy measurements of their pairwise ratios is also known as the group synchronization problem, first introduced in the context of the group SO(2) of planar rotations. The usefulness of synchronization over the group Z(2) has been demonstrated in recent algorithms for localization of sensor networks and three-dimensional structuring of molecules. In this paper, we focus on synchronization over Z(2), and consider the problem of identifying communities in a multiplex network when the interaction between the nodes is described by a signed (and possibly weighted) measure of similarity, and when the multiplex network has a natural partition into two communities, of possibly different sizes. In the setting where one has the additional information that certain subsets of nodes represent the same (unknown) group element, we consider and compare several algorithms for synchronization over Z(2), based on spectral and SDP relaxations, and message passing algorithms. In other words, all nodes within such a subset represent the same unknown group element, and one has available noisy pairwise measurements between pairs of nodes that belong to different non-overlapping subsets. Following a recent analysis of the eigenvector method for synchronization over SO(2), we analyse the robustness to noise of the eigenvector method for synchronization over Z(2), when the underlying graph of pairwise measurements is the Erdos-Renyi random graph, using results from the random matrix theory literature on the largest eigenvalue of rank-1 deformation of large random matrices. We also propose a message passing synchronization algorithm, inspired by the standard belief propagation algorithm, that outperforms the existing eigenvector synchronization algorithm only for certain classes of graphs and noise models, and enjoys the flexibility of incorporating additional constraints that may not be easily accommodated by any of the other spectral or SDP-based methods. We apply

关键词： eigenvectors group synchronization semidefinite programming multiplex networks spectral algorithms random matrix theory bipartite networks message passing algorithms voting networks

来源：评论

学校读者我要写书评

暂无评论

A spectral technique for random satisfiable 3CNF formulas

引用

RANDOM STRUCTURES & algorithms 2008年第4期32卷 519-534页

作者： Flaxman, Abraham Microsoft Res Redmond WA 98052 USA

Let I be a random 3CNF formula generated by choosing a truth assignment phi for variables x(1),...,x, uniformly at random and including every clause with i literals set true by phi with probability p(i), independently. We show that for any constants 0 <= eta(2),eta(3) <= 1 there is a constant d(min) so that for all d >= d(min) a spectral algorithm similar to the graph coloring algorithm of Alon and Kahale will find a satisfying assignment with high probability for p(1) = d/n(2), p(2) = eta(2)d/n(2), and p(3) = eta(3)d/n(2). Appropriately setting the eta(i)'s yields natural distributions on satisfiable 3CNFs, not-all-equal-sat 3CNFs, and exactly-one-sat 3CNFs. (c) 2008 Wiley Periodicals, Inc.

关键词： average-case analysis satisfiability spectral algorithms

来源：评论

学校读者我要写书评

暂无评论

Use of hyperspectral imaging to distinguish normal, precancerous, and cancerous cells

引用

CANCER CYTOPATHOLOGY 2008年第1期114卷 13-21页

作者： Siddiqi, Anwer M. Li, Hui Faruque, Fazlay Williams, Worth Lai, Kent Hughson, Michael Bigler, Steven Beach, James Johnson, William Univ Mississippi Med Ctr Dept Pathol Jackson MS 39216 USA Univ Mississippi Med Ctr Geog Informat Syst Jackson MS 39216 USA Univ Miami Miller Sch Med Dept Pediat Dr John T Macdonald Fdn Ctr Med Genet Miami FL 33152 USA NASA Stennis Space Ctr Inst Technol Dev Stennis MS USA Univ Mississippi Med Ctr Dept Biomed Stat Jackson MS 39216 USA

BACKGROUND. The objective of the current study was to test the hypothesis that the cytologic diagnosis of cancer cells can be enhanced by the technique of hyperspectral imaging (HSI). METHODS. As a proof of principle, HSI was employed to obtain hyperspectrum from a normal human fibroblast, as well as its telomerase-immortalized and SV40-transformed derivatives. Novel algorithms were developed to differentiate among these cell models based on spectral and spatial differences. Using the same technique with modified algorithms, the authors were able to differentiate among normal and precancerous (low-grade [LG] and high-grade [HG]) cervical cells and squamous cell carcinoma (SCC) on liquid-based Papanicolaou (Pap) test slides. RESULTS. The specificity for identifying normal fibroblast cell type based on spatial and spectral algorithms was 74.2%. The sensitivity for identifying telomerase-immortalized and SV40 -transformed cells was 100% and 90.3%, respectively. The system identified normal cervical cells with a specificity of 95.8%. With regard to LG precancerous cells and HG precancerous cells, the sensitivity was 66.7% and 93.5%, respectively. The sensitivity detected for SCC was 98.6%. CONCLUSIONS. HSI can be utilized in prescreening liquid-based Pap test slides to improve efficiency in Pap test diagnoses with the goal of ultimately reducing the mortality from cervical cancer while reducing health care costs.

关键词： hyperspectral imaging Papanicolaou test cervical cancer cytology dysplasia precancerous computer detection spectral algorithms spatial algorithms

来源：评论

学校读者我要写书评

暂无评论

Graph Powering and spectral Robustness

引用

SIAM JOURNAL ON MATHEMATICS OF DATA SCIENCE 2020年第1期2卷 132-157页

作者： Abbe, Emmanuel Boix-Adsera, Enric Ralli, Peter Sandon, Colin Ecole Polytech Fed Lausanne Math & Comp & Commun Sci CH-1015 Lausanne Switzerland MIT Elect Engn & Comp Sci Cambridge MA 02139 USA Princeton Univ PACM Program Appl & Computat Sci Princeton NJ 08544 USA

spectral algorithms, such as principal component analysis and spectral clustering, rely on the extremal eigenpairs of a matrix A. However, these may be uninformative without preprocessing A with a proper transformation. The reason is that the spectrum of A may be contaminated by top eigenvalues resulting from scale variations in the data, such as high-degree nodes. Designing a good psi and establishing what good means is often challenging and model dependent. This paper proposes a simple and generic construction for sparse graphs, psi(A) = 1((I + A)(r) >= 1), where A denotes the adjacency matrix, r is an integer, and the indicator function is applied entrywise. We support this "graph powering" construction with the following regularization properties: (i) if the graph is drawn from the sparse Erdos-Renyi ensemble, which has no spectral gap, then graph powering produces a "maximal" spectral gap, comparable to that obtained when powering a random regular graph;(ii) if the graph is drawn from the sparse stochastic block model, graph powering achieves the fundamental limit for weak recovery (the Kesten-Stigum threshold), settling at the same time a related conjecture by Massoulie in 2013;(iii) we also demonstrate that graph powering is significantly more robust to tangles and cliques than previous spectral algorithms based on self-avoiding or nonbacktracking walk counts, using a geometric block model as our benchmark and introducing new conjectures for this model.

关键词： community detection stochastic block models random graphs spectral algorithms network data analysis spectral embeddings

来源：评论

学校读者我要写书评

暂无评论

spectral Approaches to Nearest Neighbor Search 55

Spectral Approaches to Nearest Neighbor Search

引用

55th Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Abdullah, Amirali Andoni, Alexandr Kannan, Ravindran Krauthgamer, Robert Univ Utah Salt Lake City UT 84112 USA Weizmann Inst Sci Rehovot Israel

ISBN: (纸本)9781479965175

We study spectral algorithms for the high-dimensional Nearest Neighbor Search problem (NNS). In particular, we consider a semi-random setting where a dataset is chosen arbitrarily from an unknown subspace of low dimension, and then perturbed by full-dimensional Gaussian noise. We design spectral NNS algorithms whose query time depends polynomially on the dimension and logarithmically on the size of the point set. These spectral algorithms use a repeated computation of the top PCA vector/subspace, and are effective even when the random-noise magnitude is much larger than the interpoint distances. Our motivation is that in practice, a number of spectral NNS algorithms outperform the random-projection methods that seem otherwise theoretically optimal on worst-case datasets. In this paper we aim to provide theoretical justification for this disparity. The full version of this extended abstract is available on arXiv.

关键词： Algorithm design and analysis Data structures Nearest neighbor searches Noise Partitioning algorithms Principal component analysis Vectors Nearest neighbor search spectral algorithms Nearest neighbor query Algorithm design and analysis Partitioning algorithms Data structures principal components analysis Noise

来源：评论

学校读者我要写书评

暂无评论

A Robust spectral Algorithm for Overcomplete Tensor Decomposition 32

A Robust Spectral Algorithm for Overcomplete Tensor Decompos...

引用

32nd Conference on Learning Theory (COLT) part of the ACM Federated Computing Research Conference

作者： Hopkins, Samuel B. Schramm, Tselil Shi, Jonathan Cornell Univ Ithaca NY 14853 USA Univ Calif Berkeley Berkeley CA 94720 USA MIT Cambridge MA 02139 USA Harvard Cambridge MA 02138 USA

We give a spectral algorithm for decomposing overcomplete order-4 tensors, so long as their components satisfy an algebraic non-degeneracy condition that holds for nearly all (all but an algebraic set of measure 0) tensors over (R-d)(circle times 4) with rank n <= d(2). Our algorithm is robust to adversarial perturbations of bounded spectral norm. Our algorithm is inspired by one which uses the sum-of-squares semidefinite programming hierarchy (Ma, Shi, and Steurer STOC'16), and we achieve comparable robustness and overcompleteness guarantees under similar algebraic assumptions. However, our algorithm avoids semidefinite programming and may be implemented as a series of basic linearalgebraic operations. We consequently obtain a much faster running time than semidefinite programming methods: our algorithm runs in time (O) over tilde (n(2)d(3)) <= (O) over tilde (d(7)), which is subquadratic in the input size d(4) (where we have suppressed factors related to the condition number of the input tensor).

关键词： overcomplete tensors tensor rank decomposition CP decomposition spectral algorithms algebraic non-degeneracy sum-of-squares proofs

来源：评论

学校读者我要写书评

暂无评论

Fast algorithm for overcomplete order-3 tensor decomposition 35

Fast algorithm for overcomplete order-3 tensor decomposition

引用

35th Conference on Learning Theory (COLT)

作者： Ding, Jingqiu d'Orsi, Tommaso Liu, Chih-Hung Steurer, David Tiegel, Stefan Univ Str 6 CH-8006 Zurich Switzerland

We develop the first fast spectral algorithm to decompose a random third-order tensor over R-d of rank up to O(d(3/2)/polylog(d)). Our algorithm only involves simple linear algebra operations and can recover all components in time O (d(6.05)) under the current matrix multiplication time. Prior to this work, comparable guarantees could only be achieved via sum-of-squares [Ma, Shi, Steurer 2016]. In contrast, fast algorithms [Hopkins, Schramm, Shi, Steurer 2016] could only decompose tensors of rank at most O(d(4/3)/polylog(d)). Our algorithmic result rests on two key ingredients. A clean lifting of the third-order tensor to a sixth-order tensor, which can be expressed in the language of tensor networks. A careful decomposition of the tensor network into a sequence of rectangular matrix multiplications, which allows us to have a fast implementation of the algorithm.

关键词： Overcomplete tensor decomposition spectral algorithms tensor networks

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：