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

16th International Conference on Web Search and Data Mining

作者： Merchant, Arpit Mathioudakis, Michael Wang, Yanhao Univ Helsinki Helsinki Finland East China Normal Univ Shanghai Peoples R China

ISBN: (纸本)9781450394079

Graph summarization via node grouping is a popular method to build concise graph representations by grouping nodes from the original graph into supernodes and encoding edges into superedges such that the loss of adjacency information is minimized. Such summaries have immense applications in large-scale graph analytics due to their small size and high query processing efficiency. In this paper, we reformulate the loss minimization problem for summarization into an equivalent integer maximization problem. By initially allowing relaxed (fractional) solutions for integer maximization, we analytically expose the underlying connections to the spectral properties of the adjacency matrix. Consequently, we design an algorithm called SpecSumm that consists of two phases. In the first phase, motivated by spectral graph theory, we apply k-means clustering on the k largest (in magnitude) eigenvectors of the adjacency matrix to assign nodes to supernodes. In the second phase, we propose a greedy heuristic that updates the initial assignment to further improve summary quality. Finally, via extensive experiments on 11 datasets, we show that SpecSumm efficiently produces high-quality summaries compared to state-of-the-art summarization algorithms and scales to graphs with millions of nodes.

关键词： Graph Summarization spectral algorithms Clustering

来源：评论

学校读者我要写书评

暂无评论

Robust Recovery for Stochastic Block Models, Simplified and Generalized 2024

Robust Recovery for Stochastic Block Models, Simplified and ...

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Mohanty, Sidhanth Raghavendra, Prasad Wu, David X. MIT Cambridge MA 02139 USA Univ Calif Berkeley Berkeley CA USA

ISBN: (纸本)9798400703836

We study the problem of robust community recovery: efficiently recovering communities in sparse stochastic block models in the presence of adversarial corruptions. In the absence of adversarial corruptions, there are efficient algorithms when the signal-to-noise ratio exceeds the Kesten-Stigum (KS) threshold, widely believed to be the computational threshold for this problem. The question we study is: does the computational threshold for robust community recovery also lie at the KS threshold? We answer this question affirmatively, providing an algorithm for robust community recovery for arbitrary stochastic block models on any constant number of communities, generalizing the work of Ding, d'Orsi, Nasser & Steurer on an efficient algorithm above the KS threshold in the case of 2-community block models. (1) The Bethe Hessian of the graph is defined as H-G(t). (=(Delta)) D-G- I)t(2) + A(G)t where D-G is the diagonal matrix of degrees and A(G) is the adjacency matrix. Empirical work suggested that the Bethe Hessian for the stochastic block model has outlier eigenvectors corresponding to the communities right above the Kesten-Stigum threshold. We formally confirm the existence of outlier eigenvalues for the Bethe Hessian, by explicitly constructing outlier eigenvectors from the community vectors. (2) We develop an algorithm for a variant of robust PCA on sparse matrices. Specifically, an algorithm to partially recover top eigenspaces from adversarially corrupted sparse matrices under mild delocalization constraints. (3) A rounding algorithm to turn vector assignments of vertices into a community assignment, inspired by the algorithm of Charikar & Wirth for 2XOR.

关键词： robust inference stochastic block model community detection spectral algorithms

来源：评论

学校读者我要写书评

暂无评论

Imposing equilibrium restrictions in the estimation of dynamic discrete games

引用

QUANTITATIVE ECONOMICS 2021年第4期12卷 1223-1271页

作者： Aguirregabiria, Victor Marcoux, Mathieu Univ Toronto Dept Econ Toronto ON Canada CEPR London England Univ Montreal Dept Sci Econ CIREQ Montreal PQ Canada CIRANO Montreal PQ Canada

Imposing equilibrium restrictions provides substantial gains in the estimation of dynamic discrete games. Estimation algorithms imposing these restrictions have different merits and limitations. algorithms that guarantee local convergence typically require the approximation of high-dimensional Jacobians. Alternatively, the Nested Pseudo-Likelihood (NPL) algorithm is a fixed-point iterative procedure, which avoids the computation of these matrices, but-in games-may fail to converge to the consistent NPL estimator. In order to better capture the effect of iterating the NPL algorithm in finite samples, we study the asymptotic properties of this algorithm for data generating processes that are in a neighborhood of the NPL fixed-point stability threshold. We find that there are always samples for which the algorithm fails to converge, and this introduces a selection bias. We also propose a spectral algorithm to compute the NPL estimator. This algorithm satisfies local convergence and avoids the approximation of Jacobian matrices. We present simulation evidence and an empirical application illustrating our theoretical results and the good properties of the spectral algorithm.

关键词： Dynamic discrete games nested pseudo-likelihood fixed-point algorithms spectral algorithms convergence convergence selection bias C13 C57 C61 C73

来源：评论

学校读者我要写书评

暂无评论

Robust Estimation for Random Graphs 35

Robust Estimation for Random Graphs

引用

35th Conference on Learning Theory (COLT)

作者： Acharya, Jayadev Jain, Ayush Kamath, Gautam Suresh, Ananda Theertha Zhang, Huanyu Cornell Univ Sch Elect & Comp Engn Ithaca NY 14853 USA Univ Calif San Diego Sch Elect & Comp Engn San Diego CA USA Univ Waterloo Cheriton Sch Comp Sci Waterloo ON Canada Google Res New York NY USA Meta Menlo Pk CA USA

We study the problem of robustly estimating the parameter p of an Erdos-Renyi random graph on n nodes, where a gamma fraction of nodes may be adversarially corrupted. After showing the deficiencies of canonical estimators, we design a computationally-efficient spectral algorithm which estimates p up to accuracy (O) over tilde (root(1-p)/n+gamma root p(1-p)/root n +gamma/n) for gamma < 1/60. Furthermore, we give an inefficient algorithm with similar accuracy for all gamma < 1/2, the information-theoretic limit. Finally, we prove a nearly-matching statistical lower bound, showing that the error of our algorithms is optimal up to logarithmic factors.

关键词： random graphs robust estimation spectral algorithms

来源：评论

学校读者我要写书评

暂无评论

On statistical inference when fixed points of belief propagation are unstable 62

On statistical inference when fixed points of belief propaga...

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Liu, Siqi Mohanty, Sidhanth Raghavendra, Prasad Univ Calif Berkeley Berkeley CA 94720 USA

ISBN: (纸本)9781665420556

Many statistical inference problems correspond to recovering the values of a set of hidden variables from sparse observations on them. For instance, in a planted constraint satisfaction problem such as planted 3-SAT, the clauses are sparse observations from which the hidden assignment is to be recovered. In the problem of community detection in a stochastic block model, the community labels are hidden variables that are to be recovered from the edges of the graph. Inspired by ideas from statistical physics, the presence of a stable fixed point for belief propogation has been widely conjectured to characterize the computational tractability of these problems. For community detection in stochastic block models, many of these predictions have been rigorously confirmed. In this work, we consider a general model of statistical inference problems that includes both community detection in stochastic block models, and all planted constraint satisfaction problems as special cases. We carry out the cavity method calculations from statistical physics to compute the regime of parameters where detection and recovery should be algorithmically tractable. At precisely the predicted tractable regime, we give: (i) a general polynomial-time algorithm for the problem of detection: distinguishing an input with a planted signal from one without;(ii) a general polynomial-time algorithm for the problem of recovery: outputting a vector that correlates with the hidden assignment significantly better than a random guess would. Analogous to the spectral algorithm for community detection [1], [2], the detection and recovery algorithms are based on the spectra of a matrix that arises as the derivatives of the belief propagation update rule. To devise a spectral algorithm in our general model, we obtain bounds on the spectral norms of certain families of random matrices with correlated and matrix valued entries. We then demonstrate how eigenvectors of various powers of the matrix can be used to p

关键词： statistical inference belief propagation random graphs constraint satisfaction problems statistical physics spectral algorithms random matrices

来源：评论

学校读者我要写书评

暂无评论

The power of sum-of-squares for detecting hidden structures 58

The power of sum-of-squares for detecting hidden structures

引用

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

作者： Hopkins, Samuel B. Kothari, Pravesh K. Potechin, Aaron Raghavendra, Prasad Schramm, Tselil Steurer, David Cornell Ithaca NY 14850 USA IAS Princeton NJ USA Princeton Princeton NJ USA Univ Calif Berkeley Berkeley CA USA

ISBN: (纸本)9781538634646

We study planted problems-finding hidden structures in random noisy inputs-through the lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of powerful semidefinite programs has recently yielded many new algorithms for planted problems, often achieving the best known polynomial-time guarantees in terms of accuracy of recovered solutions and robustness to noise. One theme in recent work is the design of spectral algorithms which match the guarantees of SoS algorithms for planted problems. Classical spectral algorithms are often unable to accomplish this: the twist in these new spectral algorithms is the use of spectral structure of matrices whose entries are low-degree polynomials of the input variables. We prove that for a wide class of planted problems, including refuting random constraint satisfaction problems, tensor and sparse PCA, densest-ksubgraph, community detection in stochastic block models, planted clique, and others, eigenvalues of degree-d matrix polynomials are as powerful as SoS semidefinite programs of degree d. For such problems it is therefore always possible to match the guarantees of SoS without solving a large semidefinite program. Using related ideas on SoS algorithms and low-degree matrix polynomials (and inspired by recent work on SoS and the planted clique problem [BHK+ 16]), we prove a new SoS lower bound for the tensor PCA problem.

关键词： sum of squares semidefinite programming average-case algorithms average-case hardness spectral algorithms

来源：评论

学校读者我要写书评

暂无评论

Exploring the Spectra of Some Classes of Singular Integral Operators with Symbolic Computation

引用

MATHEMATICS IN COMPUTER SCIENCE 2016年第2期10卷 291-309页

作者： Conceicao, Ana C. Pereira, Jose C. Univ Algarve Ctr Funct Anal Linear Struct & Applicat CEAFEL Fac Ciencias & Tecnol Dept Matemat P-8005139 Faro Portugal Univ Algarve Ctr Funct Anal Linear Struct & Applicat CEAFEL Ctr Environm & Sustainabil Res CENSE Dept Engn Elect & InformatFac Ciencias & Tecnol P-8005139 Faro Portugal

spectral theory has many applications in several main scientific research areas (structural mechanics, aeronautics, quantum mechanics, ecology, probability theory, electrical engineering, among others) and the importance of its study is globally acknowledged. In recent years, several software applications were made available to the general public with extensive capabilities of symbolic computation. These applications, known as computer algebra systems (CAS), allow to delegate to a computer all, or a significant part, of the symbolic calculations present in many mathematical algorithms. In our work we use the CAS Mathematica to implement for the first time on a computer analytical algorithms developed by us and others within the Operator Theory. The main goal of this paper is to show how the symbolic computation capabilities of Mathematica allow us to explore the spectra of several classes of singular integral operators. For the one-dimensional case, nontrivial rational examples, computed with the automated process called [ASpecPaired-Scalar], are presented. For the matrix case, nontrivial essentially bounded and rational examples, computed with the analytical algorithms [AFact], [SInt], and [ASpecPaired-Matrix], are presented. In both cases, it is possible to check, for each considered paired singular integral operator, if a complex number (chosen arbitrarily) belongs to its spectrum.

关键词： spectral algorithms Factorization algorithms Paired singular integral operators Essentially bounded matrix functions Rational matrix functions Wolfram Mathematica

来源：评论

学校读者我要写书评

暂无评论

Strongly Refuting Random CSPs Below the spectral Threshold 2017

Strongly Refuting Random CSPs Below the Spectral Threshold

引用

49th Annual ACM-SIGACT Symposium on Theory of Computing (STOC)

作者： Raghavendra, Prasad Rao, Satish Schramm, Tselil Univ Calif Berkeley Berkeley CA 94720 USA

ISBN: (纸本)9781450345286

Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with n variables and m clauses, there is a value of m = Omega(n) beyond which the CSP will be unsatisfiable with high probability. Strong refutation is the problem of certifying that no variable assignment satisfies more than a constant fraction of clauses;this is the natural algorithmic problem in the unsatisfiable regime (when m/n = omega(1)). Intuitively, strong refutation should become easier as the clause density m/n grows, because the contradictions introduced by the random clauses become more locally apparent. For CSPs such as k-SAT and k-XOR, there is a long-standing gap between the clause density at which efficient strong refutation algorithms are known, m/n >= (O) over tilde (n(k/2-1)), and the clause density at which instances become unsatisfiable with high probability, m/n = omega(1)). In this paper, we give spectral and sum-of-squares algorithms for strongly refuting random k-XOR instances with clause density m/n >= (O) over tilde (n(k/2-1(1-delta))) in time exp((O) over tilde (n(delta)) or in (O) over tilde (n(delta)) rounds of the sum-of-squares hierarchy, for any delta is an element of[0, 1] and any integer k >= 3. Our algorithms provide a smooth transition between the clause density at which polynomial-time algorithms are known at delta = 0, and brute-force refutation at the satisfiability threshold when delta = 1. We also leverage our k-XOR results to obtain strong refutation algorithms for SAT (or any other Boolean CSP) at similar clause densities. Our algorithms match the known sum-of-squares lower bounds due to Grigoriev and Schonebeck, up to logarithmic factors.

关键词： Strong refutation random constraint satisfaction problems sum-of-squares hierarchy spectral algorithms

来源：评论

学校读者我要写书评

暂无评论

Social Event Magnitudes via Background Influences and Engagement Capacities and its Applications 2019

Social Event Magnitudes via Background Influences and Engage...

引用

9th International Conference on Web Intelligence, Mining and Semantics (WIMS)

作者： Liu, Kwei-guu Liu, Jyi-Shane Natl Chengchi Univ Dept Comp Sci Taipei Taiwan Natl Chengchi Univ Dept Comp Sci Taipei Taiwan Pervas Artificial Intelligence Res PAIR Labs Taichung Taiwan

ISBN: (纸本)9781450361903

Outbreaks of social events can be viewed from two angles: anomalous changes of information or popular actions. Event detection algorithms focus on the former one, while the later one is measured by social event intensity, which is a rate to show how popular an action is in a social network at a given time. The rate is relatively intuitive and can give a holistic view about activity levels in a network, but its estimation isn't easy. Inspired by event detection algorithms, this study proposes an alternative measure, social event magnitude, by using the product of background influence and cooperation value. Background influence is extracted via non-backtracking matrices, and cooperation value is obtained via engagement capacities. This alternative measure does not just integrate multisource information, but also gives a holistic view about activity levels in a network. Social event magnitudes follow a long-tailed distribution;they can be visualized for changing activities and can be applied to online event detections.

关键词： Online Event Detection Engagement Capacities Non-Backtracking Matrix spectral algorithms

来源：评论

学校读者我要写书评

暂无评论

Multiway spectral Partitioning and Higher-Order Cheeger Inequalities

引用

JOURNAL OF THE ACM 2014年第6期61卷 37-37页

作者： Lee, James R. Gharan, Shayan Oveis Trevisan, Luca Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA Stanford Univ Stanford CA 94305 USA

A basic fact in spectral graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero. Cheeger's inequality and its variants provide an approximate version of the latter fact;they state that a graph has a sparse cut if and only if there are at least two eigenvalues that are close to zero. It has been conjectured that an analogous characterization holds for higher multiplicities: There are k eigenvalues close to zero if and only if the vertex set can be partitioned into k subsets, each defining a sparse cut. We resolve this conjecture positively. Our result provides a theoretical justification for clustering algorithms that use the bottom k eigenvectors to embed the vertices into R-k, and then apply geometric considerations to the embedding. We also show that these techniques yield a nearly optimal quantitative connection between the expansion of sets of size nI k and 4, the kth smallest eigenvalue of the normalized Laplacian, where n is the number of vertices. In particular, we show that in every graph there are at least k/2 disjoint sets (one of which will have size at most 2n/k), each having expansion at most O(root lambda(k) logk). Louis, Raghavendra, Tetali, and Vempala have independently proved a slightly weaker version of this last result. The root log k bound is tight, up to constant factors, for the "noisy hypercube" graphs. Categories and Subject Descriptors: F.2.2 [Analysis of algorithms and Problem Complexity]: Nonnumerical algorithms and Problems;G.1.8 [Numerical Analysis]: Partial Differential Equations spectral methods

关键词： algorithms Theory Cheeger's inequality spectral clustering spectral algorithms sparsest cut

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：