Network embedding (NE) aims to learn low dimensional node representations, wherein both neural-based (NNE) and factorization-based (FNE) methods commonly employ negative sampling (NS) as an essential component. However, the role of NS differs markedly between these two paradigms: in NNE, negative samples are randomly chosen to facilitate efficient training, while in FNE, the distribution of negative samples plays a pivotal role in deriving the factorized matrix. In this work, we propose LocAPS (Loccal cluster-based Adaptive Positive Sampling), a novel sampling strategy that adaptively determines positive samples for each node based on local clustering. Building on LocAPS, we develop an enhanced NNE method, VERSE+, which achieves both sampling and training in linear time. For FNE, we introduce an adaptive negative sampling distribution derived from LocAPS, which tailors the sampling probability for each node. This distribution informs the construction of a factorized matrix that adaptively retains information from the similarity matrix. Moreover, its node-wise nature enables the development of FREDE+, an efficient streaming-style NE method with linear time and space complexity. We conduct extensive experiments on multiple real-world datasets, evaluating our methods on node classification and link prediction tasks, demonstrating their effectiveness and superior performance.

Attributed network embedding (ANE) can learn low-dimensional embeddings for nodes in attributed graphs, which can facilitate several data analysis tasks. However, the existing ANE methods fail to tackle scenarios involving the continuous generation of attributes. The ongoing generation of attributes accumulates numerous attributes, incurring high storage costs in existing methods. Furthermore, due to storage limitations, old attributes will be discarded as new ones are generated, existing methods struggle to integrate the new attribute information into embeddings generated from old attributes. Therefore, we propose a novel ANE framework named SANE (Streaming-style ANE), featuring a “memory” capability - that is, when updating the embeddings for new attributes, old attribute information can be partly preserved. In SANE, we first define forward and backward affinity between nodes and attributes by reviewing a node as source or target node. The definition guides quick computation of affinity vectors that integrate both topological and attribute information. Meanwhile, we propose an augmentation strategy to enrich node attribute information for enhance the quality of node embeddings. Leveraging the augmented attributes, we iteratively generate forward and backward affinity vectors, providing quantification of node-attribute affinity in two directions. Subsequently, we achieve a streaming-style update of node embeddings by employing matrix sketching technology on these iteratively generated vectors. Furthermore, capitalizing on the mergeability of matrix sketching, we efficiently integrate information of new generated attributes into node embeddings. Extensive experiments on 5 real datasets demonstrate that SANE surpasses the state-of-the-art algorithms in node classification and link prediction. SANE's ability to incorporate new attribute information into embeddings in a fast manner is validated through adequate simulation experiments.

In this paper, we propose neural-symbolic graph databases (NSGDs) that extends traditional graph data with content and structural embeddings in every node. The content embeddings can represent unstructured data (e.g., images, videos, and texts), while structural embeddings can be used to deal with incomplete graphs. We can advocate machine learning models (e.g., deep learning) to transform unstructured data and graph nodes to these embeddings. NSGDs can support a wide range of applications (e.g., online recommendation and natural language question answering) in social-media networks, multi-modal knowledge graphs and etc. As a typical search over graphs, we study subgraph search over a large NSGD, called neural-symbolic subgraph matching (NSMatch) that includes a novel ranking search function. Specifically, we develop a general algorithmic framework to process NSMatch efficiently. Using real-life multi-modal graphs, we experimentally verify the effectiveness, scalability and efficiency of NSMatch.