A specific sparse post-processing pipeline for Random Indexing on kinship analogies in a small fairytales corpus is studied; the results do not establish a generally effective embedding method.
Abstract
We study a specific sparse post-processing pipeline for Random Indexing (RI) on kinship analogies in a small fairytales corpus. The published artifacts use uniform RI context accumulation with 200 dimensions and eight nonzeros, followed by one residual graph average, $\mathbf{E}=(1-\alpha)\mathbf{E}_0+\alpha\mathbf{P}\mathbf{E}_0$, where $\mathbf{P}$ is a row-normalized PPMI graph and $\alpha=0.3$. Terminal row normalization and per-dimension median/IQR scaling are then applied. On the Google analogy benchmark's family section, 272 of 506 questions are valid for every seed. Across five paired seeds, the complete pipeline raises accuracy from 19.41\% to 30.74\%, a gain of 11.32 percentage points with a nested-bootstrap 95\% confidence interval of [6.93, 15.89]. Robust scaling alone contributes 3.24 points [1.25, 5.38], while graph averaging without robust scaling contributes 6.18 points [2.63, 9.92]. A separate 40-question general grid does not support a general improvement: the full pipeline changes accuracy by -6.00 points [-13.50, -0.50], and averaging without robust scaling changes it by -6.50 points [-14.50, -0.50]. The supported positive claim is therefore limited to the covered fairytales kinship analogy set; the results do not establish a generally effective embedding method.
It is proved that, as long as $p=o(\log n /n)$, for any $\varepsilon>0$, one can construct a confidence set of vertices of size $K(\varepsilon)$ that depends only on $\varepsilon$ and not on $n$, such that it contains the root with probability at least $1-\varepsilon$.
Luc Devroye, Gábor Lugosi, Neeladri Maitra· 1 citation· ⚡1
Graph attention normalizes neighborhood scores with softmax, the maximum-entropy choice under Shannon statistics. But homophilic and heterophilic graphs want different attention shapes, and one fixed normalization cannot serve both. We propose \textbf{LTGA} (\textbf{L}earnable \textbf{T}sallis \textbf{G}raph \textbf{A}ttention), a graph attention layer whose Tsallis entropic index $q$ is learned jointly with the weights, interpolating continuously between heavy-tailed ($q\!<\!1$), softmax ($q\!=\!1$) and compact-support ($q\!>\!1$) attention at four granularities from a global scalar to a per-edge index, under a bounded reparameterization that starts every model at the GAT baseline. Across eight benchmarks at ten seeds, LTGA-Edge takes the best average rank ($2.75$), but the omnibus test does not reject ($p\!=\!0.199$) and learning $q$ does not beat searching it: a validation-tuned frozen grid reaches $61.4\%$, tuned $\alpha$-entmax $62.2\%$ and a capacity-matched $q\!\equiv\!1$ control $62.0\%$, against $61.7\%$ for LTGA-Edge. What the learned index buys is one run instead of a grid, and an interpretable mechanism: where $q$ leaves $1$, it prunes $42\%$ of attention coefficients to exactly zero, and those edges are selectively the wrong ones, restoring them costs $7.1$ points, while random pruning at the same rate costs $13.0$ more. Project page: https://kleyt0n.github.io/ltga
This work refine the existing parameter estimation guarantees under the fatness assumption, improving the prior sample complexity to $O( \log n / \epsilon^2)$ for $\ell_\infty$-recovery, matching the untruncated minimax rate.
Rohan Chauhan, Ioannis Panageas· arXiv.org· 0 citations
A comprehensive fine-grained complexity map of MCS on both unweighted and weighted graphs is developed and the results strictly delineate the algorithmic boundaries of consistent subset selection across diverse metric structures.
R. Ganian, M. Vasilakis, Simon Wietheger· arXiv.org· 0 citations
It is proved that any dataset admits a $\gamma$-almost navigable graph with just $O\left(\frac{n}{1-\gamma}\right)$ edges, linear in the dataset size, and a randomized algorithm for constructing such a graph in near-linear time is presented.
Pratyush Avi, Christopher Musco· arXiv.org· 0 citations
Let $X_1, X_2, \ldots, X_n$ be independent random vectors. For a directed graph $G=(V,E)$ with vertex set $V=\{1,2,\ldots,n\}$ and a collection of bivariate kernels $\{h_e:e\in E\}$, we consider \[ U=\sum_{e=(i,j)\in E} h_e(X_i,X_j). \] This framework generalizes incomplete U-statistics by allowing the random vectors to be non-identically distributed, the kernels to be asymmetric and edge-dependent, and the sampling structure to be specified by an arbitrary graph. We derive several concentration inequalities for $U-\mathbb{E}U$. The main proof strategy exploits edge-coloring results from graph theory and relates the tail behavior of $U$ to the chromatic index of $G$. This approach is elementary, transparent, and readily adaptable to broader settings, including U-statistics of order $m>2$ and statistics involving doubly indexed random vectors.
Z. Ke· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
