By integrating machine learning with edge devices, we can augment the capabilities of edge devices, such as IoT devices, household appliances, and wearable technologies. These edge devices generally operate on microcontrollers with inherently limited resources, such as constrained RAM capacity and limited computational power. Nonetheless, they often process data in a high-velocity stream fashion, exemplified by sequences of activities and statuses monitored by advanced industrial sensors. In practical scenarios, models must be interpretable to facilitate troubleshooting and behavior understanding. Implementing machine learning models on edge devices is valuable and challenging, striking a balance between model efficacy and resource constraint. To address this challenge, we introduce our novel Onfesk, which combines online learning algorithms with an innovative interpretable kernel. Specifically, our Onfesk trains an online classifier over the kernel's feature sketches. Benefiting from our specially designed modules, the kernel's feature sketches can be efficiently produced, and the memory requirements of the classifier can be significantly reduced. As a result, Onfesk delivers effective and efficient performance in environments with limited resources without compromising on model interpretability. Extensive experiments with diverse real-world datasets have shown that Onfesk outperforms state-of-the-art methods, achieving up to a 7.4% improvement in accuracy within identical memory constraints.

Graph data are ubiquitous in real-world systems such as social networks and protein-protein interaction networks. In many applications, nodes usually are associated with real-value attributes, e.g., age, income, and wealth. Recently, industry and research communities have attracted attention to mining and learning attribute graphs. In this paper, we study the problem of calculating the general neighborhood cardinality of each node$v$in the graph, i.e., the sum of non-negative attribute values of the nodes in the$k$-hop neighborhood of a node$v$. The naive solution is to run a$k$-step breadth-first-search (BFS) algorithm starting from each node and storing all visited nodes' attributes. Clearly, the time complexity of this solution is$O\left(\vert V\vert d_{\max }^k\right)$, where$\vert V\vert$is the number of nodes and$d_{\max}$is the maximum node degree in the graph. In real-world networks such as Twitter,$d_{\max}$is over$3\times{1}0^{6}$. Therefore, it is infeasible to compute the neighborhood cardinality of nodes exactly in such massive networks even if we set$k=2$. To solve this problem, we propose efficient methods to compute the neighborhood cardinality of graphs with non-negative node attributes and binary node attributes, respectively. Extensive experiments on large real-world networks show the efficiency and effectiveness of our methods.

The well-known Gumbel-Max Trick for sampling elements from a categorical distribution (or more generally a non-negative vector) and its variants have been widely used in areas such as machine learning and information retrieval. To sample a random element$i$in proportion to its positive weight$v_{i}$, the Gumbel-Max Trick first computes a Gumbel random variable$g_{i}$for each positive weight element$i$, and then samples the element$i$with the largest value of$g_{i}+\ln v_{i}$. Recently, applications including similarity estimation and weighted cardinality estimation require to generate$k$independent Gumbel-Max variables from high dimensional vectors. However, it is computationally expensive for a large$k$(e.g., hundreds or even thousands) when using the traditional Gumbel-Max Trick. To solve this problem, we propose a novel algorithm,FastGM, which reduces the time complexity from$O(kn^+)$to$O(k \ln k + n^+)$, where$n^+$is the number of positive elements in the vector of interest. FastGM stops the procedure of Gumbel random variables computing for many elements, especially for those with small weights. We perform experiments on a variety of real-world datasets and the experimental results demonstrate that FastGM is orders of magnitude faster than state-of-the-art methods without sacrificing accuracy or incurring additional expenses.