Detecting Out-of-Distribution (OOD) graphs—those are drawn from a different distribution from the training data-is a critical task for ensuring the safety and reliability of Graph Neural Networks. The main challenge in unsupervised graph-level Out-of-Distribution detection lies in its common reliance on purely in-distribution (ID) data. This ID-only training paradigm leads to an incomplete characterization of the feature space, resulting in decision boundaries that lack the robustness needed to effectively separate ID from OOD samples. While incorporating synthesized outliers into the training process is a promising direction, existing generation methods are limited by their dependence on pre-defined, non-adaptive sampling heuristics (e.g., distance- or density-based). Such fixed strategies lack the flexibility to systematically explore the most informative OOD regions for refining decision boundaries. To overcome this limitation, we propose a novel Policy-Guided Outlier Synthesis (PGOS) framework that replaces static heuristics with a learned, adaptive exploration policy. PGOS trains a reinforcement learning agent to autonomously navigate low-density regions within a structured latent space, sampling representations that are maximally effective for regularizing the OOD decision boundary. These sampled points are then decoded into high-quality pseudo-OOD graphs to enhance the detector's robustness. Extensive experiments demonstrate the strong performance of our method, state-of-the-art results on multiple graph OOD and anomaly detection benchmarks.

Differentially private (DP) image synthesis enables the generation of realistic images while bounding privacy leakage, facilitating secure data sharing across organizations. However, the Gaussian noise injected during DP training, such as via DP-SGD, often severely degrades synthesis quality by disrupting model convergence. To address this, we introduce RPGen, a novel framework that enhances diffusion models' parameter robustness to mitigate DP noise effects without compromising privacy guarantees. At its core, RPGen employs adversarial model perturbation (AMP) during public pre-training to build resilience against perturbations, but we identify and tackle the critical issue of robustness transferability across domains. RPGen achieves this through a three-step process: (1) A pre-trained classifier infers labels for private images, aggregated into a class distribution noised with Gaussian mechanism for DP, and public samples are selected to match this privatized distribution for domain alignment; (2) The diffusion model is pre-trained on this curated subset with adversarial model perturbation to foster robustness; (3) The model undergoes fine-tuning on private data using DP-SGD. This synergy of robustness augmentation and transferability optimization yields high-fidelity synthesis. Extensive evaluations on ImageNet for pre-training, with CelebA and CIFAR-10 for synthesis, show RPGen outperforming state-of-the-art baselines across epsilon in 1, 5, 10. On average, it achieves 20.18% lower FID and 5.45% higher classification accuracy. Ablations confirm the efficacy of domain curation and modest perturbations, establishing RPGen as a new benchmark for privacy-utility trade-offs in image generation.

With the explosive growth of multimodal data streams on social media, the timely detection of emerging social events has become increasingly important. As a result, Multimodal Social Event Detection in open-world settings is receiving growing attention. However, most existing methods face two major limitations: (1) They overlook the dynamic nature of open-world social media data and fail to design dedicated incremental learning frameworks. (2) They ignore the impact of noise in streaming data, leading to performance degradation over long-term detection. To overcome these limitations, we propose SeInEvent (**S**tructural **E**ntropy Guided **In**cremental Learning for Open-World Multimodal Social **Event** Detection). Our innovations are as follows: **First**, considering data dynamics, we design a self-supervised alternating incremental contrastive learning mechanism. Through knowledge distillation, historical event clusters were reviewed and consolidated, and contrastive learning was combined to absorb knowledge of unknown events, ultimately achieving incremental learning without labels. **Second**, addressing the impact of noise, we propose a Pointwise Structural Entropy-based noise filter, which quantifies each sample’s informational contribution to the event clustering structure. It enables automatic removal of noisy data and supports robust long-term detection. Extensive experiments on two public datasets demonstrate that SeInEvent achieves superior performance.

Hierarchical clustering is a fundamental machine-learning technique for grouping data points into dendrograms. However, existing hierarchical clustering methods encounter two primary challenges: 1) Most methods specify dendrograms without a global objective. 2) Graph-based methods often neglect the significance of graph structure, optimizing objectives on complete or static predefined graphs. In this work, we propose Hyperbolic Continuous Structural Entropy neural networks, namely HypCSE, for structure-enhanced continuous hierarchical clustering. Our key idea is to map data points in the hyperbolic space and minimize the relaxed continuous structural entropy (SE) on structure-enhanced graphs. Specifically, we encode graph vertices in hyperbolic space using hyperbolic graph neural networks and minimize approximate SE defined on graph embeddings. To make the SE objective differentiable for optimization, we reformulate it into a function using the lowest common ancestor (LCA) on trees and then relax it into continuous SE (CSE) by the analogy of hyperbolic graph embeddings and partitioning trees. To ensure a graph structure that effectively captures the hierarchy of data points for CSE calculation, we employ a graph structure learning (GSL) strategy that updates the graph structure during training. Extensive experiments on seven datasets demonstrate the superior performance of HypCSE.

Large language models (LLMs) can effectively handle outdated information through knowledge editing.However, current approaches face two key limitations: (I) Poor generalization: Most approaches rigidly inject new knowledge without ensuring that the model can use it effectively to solve practical problems.(II) Narrow scope: Current methods focus primarily on structured fact triples, overlooking the diverse unstructured forms of factual information (e.g., news, articles) prevalent in real-world contexts.To address these challenges, we propose a new paradigm: teaching LLMs to edit knowledge via Chain of Thoughts (CoTs) reasoning (CoT2Edit).We first leverage language model agents for both structured and unstructured edited data to generate CoTs, building high-quality instruction data.The model is then trained to reason over edited knowledge through supervised finetuning (SFT) and Group Relative Policy Optimization (GRPO).At inference time, we integrate Retrieval-Augmented Generation (RAG) to dynamically retrieve relevant edited facts for real-time knowledge editing.Experimental results demonstrate that our method achieves strong generalization across six diverse knowledge editing scenarios with just a single round of training on three open-source language models.The codes are available at https:// github.com/FredJDean/CoT2Edit.

Large Reasoning Models (LRMs) can exhibit step-by-step reasoning, reflection, and backtracking, but these behaviors are often unregulated, leading to overthinking.As a result, LRMs continue generating redundant reasoning even after reaching high-confidence conclusions.This increases inference cost and latency, limiting practical deployment.The root cause is the absence of an intrinsic mechanism to monitor the reasoning state and decide when to continue, backtrack, or stop.We propose MERA, a meta-cognitive reasoning framework that decouples reasoning from control to enable independent optimization of control strategies.MERA constructs high-quality reasoning-control supervision data via a takeoverbased pipeline, and transforms long-horizon traces into structured reasoning-control alternating sequences for training.The model is trained with supervised fine-tuning to internalize the structured separation, and further optimized with Control-Segment Policy Optimization (CSPO), which combines segment-wise GRPO with control masking to focus learning on control segments.Experiments across reasoning benchmarks show that MERA improves both efficiency and accuracy.

Yuanhe Zhang, Jiayu Tian, Yibo Zhang, Shilinlu Yan, Liang Lin, Zhenhong Zhou, Li Sun, Sen Su. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Graph neural networks (GNNs) have achieved significant success in graph representation learning and have been applied to various domains. However, many real-world graphs contain sensitive personal information, such as user profiles in social networks, raising serious privacy concerns when graph learning is performed using GNNs. To address this issue, locally private graph learning protocols have gained considerable attention. These protocols leverage the privacy advantages of local differential privacy (LDP) and the effectiveness of GNN's message-passing in calibrating noisy data, offering strict privacy guarantees for users' local data while maintaining high utility (e.g., node classification accuracy) for graph learning. Despite these advantages, such protocols may be vulnerable to data poisoning attacks, a threat that has not been considered in previous research. Identifying and addressing these threats is crucial for ensuring the robustness and security of privacy-preserving graph learning frameworks. This work introduces the first data poisoning attack targeting locally private graph learning protocols. The attacker injects fake users into the protocol, manipulates these fake users to establish links with genuine users, and sends carefully crafted data to the server, ultimately compromising the utility of private graph learning. The effectiveness of the attack is demonstrated both theoretically and empirically. In addition, several defense strategies have also been explored, but their limited effectiveness highlights the need for more robust defenses.

Multimodal content on social media contains abundant cues about real-world events, and its automatic detection is critical for public safety and social governance. However, Multimodal Social Event Detection in the open world faces two major challenges: (1) They depend on supervised event labels or structured information; however, social media data in open-world settings often lack both, making it challenging for such methods to adapt to the dynamic nature of social media. (2) They rely on predefined label sets, i.e., the total number of events must generally be specified during the detection process. In contrast, in the open world, the total number of events is inherently difficult to estimate. To tackle these challenges, this paper proposes LFEvent, a label-free contrastive learning framework for Multimodal Social Event Detection. To address the first challenge, we design a label-free multimodal contrastive learning strategy that relies solely on positive samples. Specifically, we design a multimodal large language model-based semantic enhancement strategy. Leveraging carefully crafted prompts, it enriches raw image-text pairs across three dimensions -- event theme, event type, and image description -- to construct robust positive samples. Subsequently, a dedicated Siamese Network enables self-supervised cross-modal alignment and representation learning. To address the second challenge, we introduce unsupervised clustering into the MSED task for the first time. A novel structure entropy-guided hierarchical clustering method is proposed, which automatically determines the number of event clusters and enables the detection of unseen events in the training set. Experiments on multiple social media datasets demonstrate that LFEvent significantly outperforms existing methods, especially in detecting previously unseen events.

Graph neural networks (GNNs) have been extensively utilized in various fields due to their efficient and strong capability in processing graph-structured data. However, as the scale of real-world graphs continues to grow, processing large-scale graphs with GNNs has become increasingly storage-intensive and time-consuming. Graph condensation, which aims to synthesize a smaller yet informative substitute graph, has emerged as a promising solution. Most existing approaches, however, primarily focus on feature condensation while paying less attention to faithfully reconstructing structural information. Moreover, the condensed representations are typically dense, which not only limits storage and computational efficiency but also risks retaining noise and redundancy. To address these limitations, we propose DGC, a Discrete Graph Condensation framework, where numerous nodes in the original graph can be represented by the discrete codes in the codebook while maintaining the original structure information. Specifically, we leverage high-order proximity between nodes to capture the original graph's structure and transfer it to the condensed graph via low-rank approximation. Meanwhile, node features are discretized and compressed through a vector quantized variational autoencoder, effectively reducing redundancy and enhancing storage efficiency while retaining critical information. Extensive experiments on multiple real-world graphs demonstrate the effectiveness of our proposed model against nine competitive baseline methods across different condensation ratios.

Hypergraphs are the natural description of higher-order interactions among objects, widely applied in social network analysis, cross-modal retrieval, etc. Hypergraph Neural Networks (HGNNs) have become the dominant solution for learning on hypergraphs. Traditional HGNNs are extended from message passing graph neural networks, following the homophily assumption, and thus struggle with the prevalent heterophilic hypergraphs that call for long-range dependence modeling. Existing solutions enlarge the message flow through the hypergraph bottleneck, mitigating the oversquashing issue and capturing long-range dependence. However, they often accelerate the loss of representation distinguishability in the repeated aggregations, leading to oversmoothing. This dilemma motivates an interesting question: Can we develop a unified mechanism that is agnostic to both homophilic and heterophilic hypergraphs? In this paper, we achieve the best of both worlds through the lens of Riemannian geometry, which provides the potential to adjust the message passing behavior in different regions. The key insight lies in the connection between oversquashing and hypergraph bottleneck within the framework of Riemannian manifold heat flow. Building on this, we propose the novel idea of locally adapting the bottlenecks of different subhypergraphs. The core innovation of the proposed mechanism is the design of an adaptive local (heat) exchanger. Specifically, it captures the rich long-range dependencies via the Robin condition, and preserves the representation distinguishability via source terms, thereby enabling heterophily-agnostic message passing with theoretical guarantees. Based on this theoretical foundation, we present a novel Heat-Exchanger with Adaptive Locality for Hypergraph Neural Network (HealHGNN), designed as a node-hyperedge bidirectional systems with linear complexity in the number of nodes and hyperedges. Extensive experiments on both homophilic and heterophilic cases show that HealHGNN achieves the state-of-the-art performance.

Community detection is a longstanding topic in graph and Web algorithms, and semi-supervised local community detection, identifying the community to which the given user belongs, garners increasing research attention in recent years. While achieving encouraging results, existing solutions often encounter accumulated errors due to the weak supervision in the community expansion process, and are undermined by the initial seed sensitivity that a suboptimal or boundary seed node can easily misguide community generation. To fill these gaps, we propose a fresh generative perspective on hyperbolic space, which recasts this problem as the seed-conditioned sequence generation, and reformulates community generation as a continuous transport of probability distributions in the manifold measure space. In this paper, we present a novel Semi-supervised Local community detection framework based on hyperbolic Flow Matching (SLFM). Specifically, it leverages a geometric-aware Seed Selector that refines initial seeds with hyperbolic angular and radial priors, and a Hyperbolic Flow Transporter that learns a vector field to map a source distribution to a target community distribution, generating a robust set of anchors. Finally, a Community Expander is introduced to utilize these anchors as surrogate supervision to effectively recover the full community. Experimental results on four real-world datasets demonstrate that SLFM significantly outperforms existing methods in both local and global semi-supervised settings.

Abstract Graphs are ubiquitous, and graph learning has long been a fundamental topic in machine learning. While Graph Neural Networks (GNNs) have achieved remarkable results, they are typically designed for specific tasks or graphs, requiring retraining to adapt the diversity of real-world graph data. Recently, foundation models, such as Large Language Models (LLMs), have driven revolutionary progress in the language domain through universal pretraining. Their success has sparked growing interest in designing Graph Foundation Models (GFMs), a novel family of graph neural networks pre-trained on large-scale, diverse graph data, which are capable of supporting a wide range of downstream tasks on different graphs. Early efforts in the literature often adapt LLMs by transforming graph data into sequential representations. However, unlike word sequences in natural language, graphs are inherently non-Euclidean structures that encapsulate complex intercorrelations among entities. Existing GFMs often trivialize the structural diversity and complexity inherent in graph data. To address this gap, we propose to study graph foundation model from the perspective of Riemannian geometry, and design a novel Curvature-guided Riemannian Graph Foundation Model (CRGFM). To the best of our knowledge, CRGFM is the first GFM to introduce a curvature-based graph description along with geometric standardization. Specifically, to capture structural diversity, the input graph is represented using a mixture of geometric experts. A novel geometric standardization is then introduced via an augmented Lorentz transformation. To model structural complexity, we design a Riemannian graph transformer within a standardized product bundle that disentangles graph structure from node attributes. Finally, we introduce graph prompt learning on the manifold to bridge contrastive learning with downstream tasks. Extensive experiment on a diverse set of real-world graphs demonstrates the superiority of CRGFM.

Graph clustering is a longstanding topic in machine learning. In recent years, deep learning methods have achieved encouraging results, but they still require predefined cluster numbers $K$K, and typically struggle with imbalanced graphs, especially in identifying minority clusters. The limitations motivate us to study a challenging yet practical problem: deep graph clustering without $K$K considering the imbalance in reality. We approach this problem from a fresh perspective of information theory (i.e., structural information). In the literature, structural information has rarely been touched in deep clustering, and the classic definition falls short in its discrete formulation, neglecting node attributes and exhibiting prohibitive complexity. In this paper, we first establish a differentiable structural information, generalizing the discrete formalism to continuous realm, so that we design a hyperbolic deep model (LSEnet) to learn the neural partitioning tree in the Lorentz model of hyperbolic space. Theoretically, we demonstrate its capability in clustering without requiring $K$K and identifying minority clusters in imbalanced graphs. Second, we refine hyperbolic representations of the partitioning tree, enhancing graph semantics, for better clustering. Contrastive learning for tree structures is non-trivial and costs quadratic complexity. Instead, we further advance our theory by discovering an interesting fact that structural entropy indeed bounds the tree contrastive loss. Finally, with an efficient reformulation, we approach graph clustering through a novel augmented structural information learning (ASIL), which offers a simple yet effective objective of augmented structural entropy to seamlessly integrates hyperbolic partitioning tree construction and contrastive learning. With a provable improvement in graph conductance, ASIL achieves effective debiased graph clustering in linear complexity with respect to the graph size. Extensive experiments show the ASIL outperforms 20 strong baselines by an average of $+12.42\%$+12.42% in NMI on Citeseer dataset.

In recent years, Message Passing Neural Networks (MPNNs) have emerged as a leading paradigm for learning over graph-structured data, owing to their simple architecture and excellent scalability. However, their expressive power is strictly limited by the one-dimensional Weisfeiler–Leman (1-WL) test. A common approach to enhance expressivity is designing models based on higher-order k -WL and k -Folklore WL ( k -FWL) tests, collectively referred to as tuple-based GNNs. Despite their greater expressive power, these methods face two major challenges: (1) The neighboring tuples in k -WL/FWL are generated by replacing any node in the graph, disregarding adjacency relationships and thus failing to capture structural dependencies between tuples. (2) The design of k -WL/FWL lacks flexibility, while increasing k enhances expressivity, it also results in an exponential surge in time and space complexity. To overcome these limitations, we propose Trail-WL, a more expressive variant of the WL test, along with its neural network counterpart, Trail-based Tuple Neural Network (TTNN). We redefine node tuples as collections of trail structures, providing a more intuitive representation of graph connectivity compared to prior tuple-based methods. By incorporating variable trail lengths and node distance constraints, our model adaptively balances expressivity and scalability while preserving essential structural features. Furthermore, we propose and formally prove three theoretical expressivity theorems for Trail-WL. Finally, we conduct comprehensive experiments on both synthetic and real-world datasets, demonstrating that our approach consistently matches or outperforms baseline methods, thereby substantiating its effectiveness.

Dynamic interacting system modeling is important for understanding and simulating real world systems, e.g., meteorology and the spread of COVID. The system is typically described as a graph, where multiple objects dynamically interact with each other and evolve over time. In recent years, graph Ordinary Differential Equations (ODE) receive increasing research attentions. While achieving encouraging results, existing solutions prioritize the traditional Euclidean space, and neglect the intrinsic geometry of the system and physics laws, e.g., the principle of entropy increasing. The aforementioned limitations motivate us to rethink the system dynamics from a fresh perspective of Riemannian geometry, and pose a more realistic problem of physics-informed dynamic system modeling, considering the underlying geometry and physics law for the first time. In this paper, we present a novel physics-informed Riemannian graph ODE for a wide range of entropy-increasing dynamic systems (termed as Pioneer). In particular, we formulate a differential system on the Riemannian manifold, where a manifold-valued graph ODE is governed by the proposed constrained Ricci flow, and a manifold preserving Gyro-transform aware of system geometry. Theoretically, we report the provable entropy non-decreasing of our formulation, obeying the physics laws. Empirical results show the superiority of Pioneer on real datasets.

Probabilistic embeddings have several advantages over deterministic embeddings as they map each data point to a distribution, which better describes the uncertainty and complexity of data. Many works focus on adjusting the distribution constraint under the Information Bottleneck (IB) principle to enhance representation learning. However, these proposed regularization terms only consider the constraint of each latent variable, omitting the structural information between latent variables. In this paper, we propose a novel structural entropy-guided probabilistic coding model, named SEPC. Specifically, we incorporate the relationship between latent variables into the optimization by proposing a structural entropy regularization loss. Besides, as traditional structural information theory is not well-suited for regression tasks, we propose a probabilistic encoding tree, transferring regression tasks to classification tasks while diminishing the influence of the transformation. Experimental results across 12 natural language understanding tasks, including both classification and regression tasks, demonstrate the superior performance of SEPC compared to other state-of-the-art models in terms of effectiveness, generalization capability, and robustness to label noise.

The vast, complex, and dynamic nature of social message data has posed challenges to social event detection (SED). Despite considerable effort, these challenges persist, often resulting in inadequately expressive message representations (ineffective) and prolonged learning durations (inefficient). In response to the challenges, this work introduces an unsupervised framework, HyperSED (Hyperbolic SED). Specifically, the proposed framework first models social messages into semantic-based message anchors, and then leverages the structure of the anchor graph and the expressiveness of the hyperbolic space to acquire structure- and geometry-aware anchor representations. Finally, HyperSED builds the partitioning tree of the anchor message graph by incorporating differentiable structural information as the reflection of the detected events. Extensive experiments on public datasets demonstrate HyperSED's competitive performance, along with a substantial improvement in efficiency compared to the current state-of-the-art unsupervised paradigm. Statistically, HyperSED boosts incremental SED by an average of 2%, 2%, and 25% in NMI, AMI, and ARI, respectively; enhancing efficiency by up to 37.41 times and at least 12.10 times, illustrating the advancement of the proposed framework.

Class-incremental event detection (CIED) is essential for real-world information extraction systems, which must continually recognize new event types without forgetting past knowledge. The main challenge lies in balancing stability and adaptability under data imbalance. Existing methods often underuse the hierarchical and syntactic structures of language, and thus limit the generalization capacity. We propose HPLLM, a hyperbolic prompt-enhanced large language model framework, motivated by the observation that both embedding distributions and dependency graphs in event datasets exhibit hyperbolic properties. HPLLM integrates two key components: (1) Hyperbolic LoRA fine-tuning, enabling geometry-aware parameter adaptation for hierarchical semantics; and (2) Hyperbolic Adaptive Graph Diffusion Convolution (HADC), which encodes syntactic dependencies into structure-aware prompts for LLMs. Together, these techniques strengthen semantic discrimination, reduce forgetting, and improve adaptation across incremental stages. Extensive experiments on ACE2005 and MAVEN demonstrate that HPLLM consistently surpasses state-of-the-art baselines in macro-F1, achieving stronger retention of old knowledge and better generalization to new event types. In particular, the model shows clear gains on rare categories with few training mentions, demonstrating its robustness in imbalanced and few-shot regimes.

Source localization, the inverse problem of information diffusion, shows fundamental importance for understanding social dynamics. While achieving notable progress, existing solutions are typically exposed to the risk of error accumulation, and require a large number of observations for effective inference. However, it is often impractical to obtain quantities of observations in real scenarios, highlighting the need for a transferable model with broad applicability. Recently, Riemannian geometry has demonstrated its effectiveness in information diffusion and offers guidance in knowledge transfer, but has yet to be explored in source localization. In light of the issues above, we propose to study transferable source localization from a fresh geometric perspective, and present a novel approach (Trace) on the Riemannian manifold. Concretely, we establish a structural Schrodinger bridge to directly model the map between source and final distributions, where a functional curvature, encapsulating the graph structure, is formulated to govern the Schrodinger bridge and facilitate domain adaptation. Furthermore, we design a simple yet effective learning algorithm for Riemannian Schrodinger bridges (geodesics bridge matching) in which we prove the optimal projection holds for Riemannian measure so that the expensive iterative procedure is avoided. Extensive experiments demonstrate the effectiveness and transferability of Trace on both synthetic and real datasets.

Research on Graph Structure Learning (GSL) provides key insights for graph-based clustering, yet current methods like Graph Neural Networks (GNNs), Graph Attention Networks (GATs), and contrastive learning often rely heavily on the original graph structure. Their performance deteriorates when the original graph's adjacency matrix is too sparse or contains noisy edges unrelated to clustering. Moreover, these methods depend on learning node embeddings and using traditional techniques like k-means to form clusters, which may not fully capture the underlying graph structure between nodes. To address these limitations, this paper introduces DeSE, a novel unsupervised graph clustering framework incorporating Deep Structural Entropy. It enhances the original graph with quantified structural information and deep neural networks to form clusters. Specifically, we first propose a method for calculating structural entropy with soft assignment, which quantifies structure in a differentiable form. Next, we design a Structural Learning layer (SLL) to generate an attributed graph from the original feature data, serving as a target to enhance and optimize the original structural graph, thereby mitigating the issue of sparse connections between graph nodes. Finally, our clustering assignment method (ASS), based on GNNs, learns node embeddings and a soft assignment matrix to cluster on the enhanced graph. The ASS layer can be stacked to meet downstream task requirements, minimizing structural entropy for stable clustering and maximizing node consistency with edge-based cross-entropy loss. Extensive comparative experiments are conducted on four benchmark datasets against eight representative unsupervised graph clustering baselines, demonstrating the superiority of the DeSE in both effectiveness and interpretability.

Message Passing Neural Networks (MPNNs) are the building block of graph foundation models, but fundamentally suffer from oversmoothing and oversquashing. There has recently been a surge of interest in fixing both issues. Existing efforts primarily adopt global approaches, which may be beneficial in some regions but detrimental in others, ultimately leading to the suboptimal expressiveness. In this paper, we begin by revisiting oversquashing through a global measure -- spectral gap $\lambda$ -- and prove that the increase of $\lambda$ leads to gradient vanishing with respect to the input features, thereby undermining the effectiveness of message passing. Motivated by such theoretical insights, we propose a local approach that adaptively adjusts message passing based on local structures. To achieve this, we connect local Riemannian geometry with MPNNs, and establish a novel nonhomogeneous boundary condition to address both oversquashing and oversmoothing. Building on the Robin condition, we design a GBN network with local bottleneck adjustment, coupled with theoretical guarantees. Extensive experiments on homophilic and heterophilic graphs show the expressiveness of GBN. Furthermore, GBN does not exhibit performance degradation even when the network depth exceeds $256$ layers.

While large language models (LLMs) can solve PhD-level reasoning problems over long context inputs, they still struggle with a seemingly simpler task: following explicit length instructions—e.g., write a 10,000-word novel. Additionally, models often generate far too short outputs, terminate prematurely, or even refuse the request. Existing benchmarks focus primarily on evaluating generations quality, but often overlook whether the generations meet length constraints. To this end, we introduce Length Instruction Following Evaluation Benchmark (LIFEBench) to comprehensively evaluate LLMs' ability to follow length instructions across diverse tasks and a wide range of specified lengths. LIFEBench consists of 10,800 instances across 4 task categories in both English and Chinese, covering length constraints ranging from 16 to 8192 words. We evaluate 26 widely-used LLMs and find that most models reasonably follow short-length instructions but deteriorate sharply beyond a certain threshold. Surprisingly, almost all models fail to reach the vendor-claimed maximum output lengths in practice, as further confirmed by our evaluations extending up to 32K words. Even long-context LLMs, despite their extended input-output windows, counterintuitively fail to improve length-instructions following. Notably, Reasoning LLMs outperform even specialized long-text generation models, achieving state-of-the-art length following. Overall, LIFEBench uncovers fundamental limitations in current LLMs' length instructions following ability, offering critical insights for future progress.

The foundation model has heralded a new era in artificial intelligence, pretraining a single model to offer cross-domain transferability on different datasets.Graph neural networks excel at learning graph data, the omnipresent non-Euclidean structure, but often lack the generalization capacity.Hence, graph foundation model is drawing increasing attention, and recent efforts have been made to leverage Large Language Models.On the one hand, existing studies primarily focus on text-attributed graphs, while a wider range of real graphs do not contain fruitful textual attributes.On the other hand, the sequential graph description tailored for the Large Language Model neglects the structural complexity, which is a predominant characteristic of the graph.Such limitations motivate an important question: Can we go beyond Large Language Models, and pretrain a universal model to learn the structural knowledge for any graph?The answer in the language or vision domain is a shared vocabulary.We observe the fact that there also exist shared substructures underlying graph domain, and thereby open a new opportunity of graph foundation model with structural vocabulary.The key innovation is the discovery of a simple yet effective structural vocabulary of trees and cycles, and we explore its inherent connection to Riemannian geometry.Herein, we present a universal pretraining model, RiemannGFM.Concretely, we first construct a novel product bundle to incorporate the diverse geometries of the vocabulary.Then, on this constructed space, we stack Riemannian layers where the structural vocabulary, regardless of specific graph, is learned in Riemannian manifold offering cross-domain transferability.Extensive experiments show the effectiveness of RiemannGFM on a diversity of real graphs.

Social Event Detection (SED) aims to identify significant events from social streams, and has a wide application ranging from public opinion analysis to risk management. In recent years, Graph Neural Network (GNN) based solutions have achieved state-of-the-art performance. However, GNN-based methods often struggle with missing and noisy edges between messages, affecting the quality of learned message embedding. Moreover, these methods statically initialize node embedding before training, which, in turn, limits the ability to learn from message texts and relations simultaneously. In this article, we approach social event detection from a new perspective based on Pre-trained Language Models (PLMs), and present \(\mathrm{RPLM}_{SED}\) ( R elational prompt-based P re-trained L anguage M odels for S ocial E vent D etection). We first propose a new pairwise message modeling strategy to construct social messages into message pairs with multi-relational sequences. Secondly, a new multi-relational prompt-based pairwise message learning mechanism is proposed to learn more comprehensive message representation from message pairs with multi-relational prompts using PLMs. Thirdly, we design a new clustering constraint to optimize the encoding process by enhancing intra-cluster compactness and inter-cluster dispersion, making the message representation more distinguishable. We evaluate the \(\mathrm{RPLM}_{SED}\) on three real-world datasets, demonstrating that the \(\mathrm{RPLM}_{SED}\) model achieves state-of-the-art performance in offline, online, low-resource, and long-tail distribution scenarios for social event detection tasks.

Graphs are typical non-Euclidean data of complex structures. In recent years, Riemannian graph representation learning has emerged as an exciting alternative to Euclidean ones. However, Riemannian methods are still in an early stage: most of them present a single curvature (radius) regardless of structural complexity, suffer from numerical instability due to the exponential/logarithmic map, and lack the ability to capture motif regularity. In light of the issues above, we propose the problem of Motif-aware Riemannian Graph Representation Learning, seeking a numerically stable encoder to capture motif regularity in a diverse-curvature manifold without labels. To this end, we present a novel Motif-aware Riemannian model with Generative-Contrastive learning (MotifRGC), which conducts a minmax game in Riemannian manifold in a self-supervised manner. First, we propose a new type of Riemannian GCN (D-GCN), in which we construct a diverse-curvature manifold by a product layer with the diversified factor, and replace the exponential/logarithmic map by a stable kernel layer. Second, we introduce a motif-aware Riemannian generative-contrastive learning to capture motif regularity in the constructed manifold and learn motif-aware node representation without external labels. Empirical results show the superiority of MofitRGC.

Unsupervised anomaly detection in time series is essential in industrial applications, as it significantly reduces the need for manual intervention. Multivariate time series pose a complex challenge due to their feature and temporal dimensions. Traditional methods use Graph Neural Networks (GNNs) or Transformers to analyze spatial while RNNs to model temporal dependencies. These methods focus narrowly on one dimension or engage in coarse-grained feature extraction, which can be inadequate for large datasets characterized by intricate relationships and dynamic changes. This paper introduces a novel temporal model built on an enhanced Graph Attention Network (GAT) for multivariate time series anomaly detection called TopoGDN. Our model analyzes both time and feature dimensions from a fine-grained perspective. First, we introduce a multi-scale temporal convolution module to extract detailed temporal features. Additionally, we present an augmented GAT to manage complex inter-feature dependencies, which incorporates graph topology into node features across multiple scales, a versatile, plug-and-play enhancement that significantly boosts the performance of GAT. Our experimental results confirm that our approach surpasses the baseline models on four datasets, demonstrating its potential for widespread application in fields requiring robust anomaly detection. The code is available at https://github.com/ljj-cyber/TopoGDN.

Cross-domain Aspect Sentiment Triplet Extraction (ASTE) aims to extract fine-grained sentiment elements from target domain sentences by leveraging the knowledge acquired from the source domain. Due to the absence of labeled data in the target domain, recent studies tend to rely on pre-trained language models to generate large amounts of synthetic data for training purposes. However, these approaches entail additional computational costs associated with the generation process. Different from them, we discover a striking resemblance between table-filling methods in ASTE and two-stage Object Detection (OD) in computer vision, which inspires us to revisit the cross-domain ASTE task and approach it from an OD standpoint. This allows the model to benefit from the OD extraction paradigm and region-level alignment. Building upon this premise, we propose a novel method named Table-Filling via Mean Teacher (TFMT). Specifically, the table-filling methods encode the sentence into a 2D table to detect word relations, while TFMT treats the table as a feature map and utilizes a region consistency to enhance the quality of those generated pseudo labels. Additionally, considering the existence of the domain gap, a cross-domain consistency based on Maximum Mean Discrepancy is designed to alleviate domain shift problems. Our method achieves state-of-the-art performance with minimal parameters and computational costs, making it a strong baseline for cross-domain ASTE.

Social event detection refers to extracting relevant message clusters from social media data streams to represent specific events in the real world. Social event detection is important in numerous areas, such as opinion analysis, social safety, and decision-making. Most current methods are supervised and require access to large amounts of data. These methods need prior knowledge of the events and carry a high risk of leaking sensitive information in the messages, making them less applicable in open-world settings. Therefore, conducting unsupervised detection while fully utilizing the rich information in the messages and protecting data privacy remains a significant challenge. To this end, we propose a novel social event detection framework, ADP-SEMEvent, an unsupervised social event detection method that prioritizes privacy. Specifically, ADP-SEMEvent is divided into two stages, i.e., the construction stage of the private message graph and the clustering stage of the private message graph. In the first stage, an adaptive differential privacy approach is used to construct a private message graph. In this process, our method can adaptively apply differential privacy based on the events occurring each day in an open environment to maximize the use of the privacy budget. In the second stage, to address the reduction in data utility caused by noise, a novel 2-dimensional structural entropy minimization algorithm based on optimal subgraphs is used to detect events in the message graph. The highlight of this process is unsupervised and does not compromise differential privacy. Extensive experiments on two public datasets demonstrate that ADP-SEMEvent can achieve detection performance comparable to state-of-the-art methods while maintaining reasonable privacy budget parameters.

Truth discovery is an effective tool for discovering the truth from a multitude of data points of varying quality, which inherently involves privacy concerns. While existing studies have predominantly focused on protecting workers’ submitted sensing data using local differential privacy (LDP), they overlook a crucial aspect of real-world scenarios: workers are likely to provide more accurate data for tasks they perceive as important, resulting in submissions that more closely approximate the truth for these tasks. Moreover, the prevalent use of the Laplace mechanism for noise addition, due to the inherent randomness and unboundedness of the Laplace distribution, might lead to excessive noise, potentially compromising the accuracy of truth discovery and yielding a noisy approximation of the truth. To address these limitations, we propose a Gaussian distribution-based truth discOvery approach under Local Differential privacy (GOLD). The algorithm’s core innovation lies in its comprehensive utilization of Gaussian distribution for both task importance and worker quality after adding Laplacian noise. Workers first apply Laplacian noise to their data locally, after which the problem is formalized as a constraint optimization task, deriving an iterative equation for the noisy truth. Theoretical analysis demonstrates that the GOLD algorithm rigorously adheres to local differential privacy requirements while achieving high truth accuracy and low time complexity. Empirical validation on two real datasets reveals that, compared to state-of-the-art algorithms, the GOLD algorithm improves the truth accuracy by at least 20%.

Task allocation, a core component of mobile crowd-sensing systems, facilitates the collection, analysis, and sharing of diverse data. While existing studies often employ planar Laplacian (PL) distribution to achieve Geo-indistinguishability (Geo-I) for worker location protection, the randomness and boundlessness of PL distribution, coupled with greedy allocation strategies, often lead to excessive noise and incomplete task assignments. Moreover, these approaches typically overlook the equilibrium between worker and server benefits. To address these challenges under Geo-I, we present the Kitty approach, which adopts Q-learning to achieve superior task allocation after formalizing a constrained optimization problem that maximizes profits for both parties. Kitty operates through three key mechanisms: 1) formalizing a constrained optimization problem based on a comprehensive analysis of both parties’ profits and a pre-defined equilibrium parameter, 2) implementing adaptive adjustment of the Q-learning greedy parameter to balance exploration and exploitation, and 3) designing two conflict resolution strategies to mitigate potential distance conflicts after location perturbation. Experiments on two real-world datasets demonstrate that Kitty outperforms the state-of-the-art by at least 15% in average travel distance reduction and 1% in task completion rate improvement.

Graph clustering is a fundamental problem in machine learning. Deep learning methods achieve the state-of-the-art results in recent years, but they still cannot work without predefined cluster numbers. Such limitation motivates us to pose a more challenging problem of graph clustering with unknown cluster number. We propose to address this problem from a fresh perspective of graph information theory (i.e., structural information). In the literature, structural information has not yet been introduced to deep clustering, and its classic definition falls short of discrete formulation and modeling node features. In this work, we first formulate a differentiable structural information (DSI) in the continuous realm, accompanied by several theoretical results. By minimizing DSI, we construct the optimal partitioning tree where densely connected nodes in the graph tend to have the same assignment, revealing the cluster struc- ture. DSI is also theoretically presented as a new graph clustering objective, not requiring the pre-defined cluster number. Furthermore, we design a neural LSEnet in the Lorentz model of hyperbolic space, where we integrate node features to structural information via manifold-valued graph convolution. Extensive empirical results on real graphs show the superiority of our approach.

Graph neural networks (GNNs) have become the dominant solution for learning on graphs, the typical non-Euclidean structures. Conventional GNNs, constructed with the Artificial Neuron Network (ANN), have achieved impressive performance at the cost of high computation and energy consumption. In parallel, spiking GNNs with brain-like spiking neurons are drawing increasing research attention owing to the energy efficiency. So far, existing spiking GNNs consider graphs in Euclidean space, ignoring the structural geometry, and suffer from the high latency issue due to Back-Propagation-Through-Time (BPTT) with the surrogate gradient. In light of the aforementioned issues, we are devoted to exploring spiking GNN on Riemannian manifolds, and present a Manifold-valued Spiking GNN (MSG). In particular, we design a new spiking neuron on geodesically complete manifolds with the diffeomorphism, so that BPTT regarding the spikes is replaced by the proposed differentiation via manifold. Theoretically, we show that MSG approximates a solver of the manifold ordinary differential equation. Extensive experiments on common graphs show the proposed MSG achieves superior performance to previous spiking GNNs and energy efficiency to conventional GNNs.

Information diffusion prediction is fundamental to understand the structure and organization of the online social networks, and plays a crucial role to blocking rumor spread, influence maximization, political propaganda, etc.So far, most existing solutions primarily predict the next user who will be informed with historical cascades, but ignore an important factor in the diffusion processthe time.Such limitation motivates us to pose the problem of the time-aware personalized information diffusion prediction for the first time, telling the time when the target user will be informed.In this paper, we address this problem from a fresh geometric perspective of Ricci curvature, and propose a novel Ricci-curvature regulated Ordinary Differential Equation (R-ODE).In the diffusion process, R-ODE considers that the inter-correlated users are organized in a dynamic system in the representation space, and the cascades give the observations sampled from the continuous realm.At each infection time, the message diffuses along the largest Ricci curvature, signifying less transportation effort.In the continuous realm, the message triggers users' movement, whose trajectory in the space is parameterized by an ODE with graph neural network.Consequently, R-ODE predicts the infection time of a target user by the movement trajectory learnt from the observations.Extensive experiments evaluate the personalized time prediction ability of R-ODE, and show R-ODE outperforms the state-of-the-art baselines.

Continual graph learning routinely finds its role in a variety of real-world applications where the graph data with different tasks come sequentially. Despite the success of prior works, it still faces great challenges. On the one hand, existing methods work with the zero-curvature Euclidean space, and largely ignore the fact that curvature varies over the com- ing graph sequence. On the other hand, continual learners in the literature rely on abundant labels, but labeling graph in practice is particularly hard especially for the continuously emerging graphs on-the-fly. To address the aforementioned challenges, we propose to explore a challenging yet practical problem, the self-supervised continual graph learning in adaptive Riemannian spaces. In this paper, we propose a novel self-supervised Riemannian Graph Continual Learner (RieGrace). In RieGrace, we first design an Adaptive Riemannian GCN (AdaRGCN), a unified GCN coupled with a neural curvature adapter, so that Riemannian space is shaped by the learnt curvature adaptive to each graph. Then, we present a Label-free Lorentz Distillation approach, in which we create teacher-student AdaRGCN for the graph sequence. The student successively performs intra-distillation from itself and inter-distillation from the teacher so as to consolidate knowledge without catastrophic forgetting. In particular, we propose a theoretically grounded Generalized Lorentz Projection for the contrastive distillation in Riemannian space. Extensive experiments on the benchmark datasets show the superiority of RieGrace, and additionally, we investigate on how curvature changes over the graph sequence.

Graph Neural Networks (GNNs) have shown great power for learning and mining on graphs, and Graph Structure Learning (GSL) plays an important role in boosting GNNs with a refined graph. In the literature, most GSL solutions either primarily focus on structure refinement with task-specific supervision (i.e., node classification), or overlook the inherent weakness of GNNs themselves (e.g., over-squashing), resulting in suboptimal performance despite sophisticated designs. In light of these limitations, we propose to study self-supervised graph structure-feature co-refinement for effectively alleviating the issue of over-squashing in typical GNNs. In this paper, we take a fundamentally different perspective of the Ricci curvature in Riemannian geometry, in which we encounter the challenges of modeling, utilizing and computing Ricci curvature. To tackle these challenges, we present a self-supervised Riemannian model, DeepRicci. Specifically, we introduce a latent Riemannian space of heterogeneous curvatures to model various Ricci curvatures, and propose a gyrovector feature mapping to utilize Ricci curvature for typical GNNs. Thereafter, we refine node features by geometric contrastive learning among different geometric views, and simultaneously refine graph structure by backward Ricci flow based on a novel formulation of differentiable Ricci curvature. Finally, extensive experiments on public datasets show the superiority of DeepRicci, and the connection between backward Ricci flow and over-squashing. Codes of our work are given in https://github.com/RiemanGraph/.

Graph clustering is a longstanding research topic, and has achieved remarkable success with the deep learning methods in recent years. Nevertheless, we observe that several important issues largely remain open. On the one hand, graph clustering from the geometric perspective is appealing but has rarely been touched before, as it lacks a promising space for geometric clustering. On the other hand, contrastive learning boosts the deep graph clustering but usually struggles in either graph augmentation or hard sample mining. To bridge this gap, we rethink the problem of graph clustering from geometric perspective and, to the best of our knowledge, make the first attempt to introduce a heterogeneous curvature space to graph clustering problem. Correspondingly, we present a novel end-to-end contrastive graph clustering model named CONGREGATE, addressing geometric graph clustering with Ricci curvatures. To support geometric clustering, we construct a theoretically grounded Heterogeneous Curvature Space where deep representations are generated via the product of the proposed fully Riemannian graph convolutional nets. Thereafter, we train the graph clusters by an augmentation-free reweighted contrastive approach where we pay more attention to both hard negatives and hard positives in our curvature space. Empirical results on real-world graphs show that our model outperforms the state-of-the-art competitors.

Sequential interaction networks (SIN) have been commonly adopted in many applications such as recommendation systems, search engines and social networks to describe the mutual influence between users and items/products. Efforts on representing SIN are mainly focused on capturing the dynamics of networks in Euclidean space, and recently plenty of work has extended to hyperbolic geometry for implicit hierarchical learning. Previous approaches which learn the embedding trajectories of users and items achieve promising results. However, there are still a range of fundamental issues remaining open. For example, is it appropriate to place user and item nodes in one identical space regardless of their inherent discrepancy? Instead of residing in a single fixed curvature space, how will the representation spaces evolve when new interaction occurs?

Social network alignment, identifying social accounts of the same individual across different social networks, shows fundamental importance in a wide spectrum of applications, such as link prediction and information diffusion. Individuals more often than not join in multiple social networks, and it is in fact much too expensive or even impossible to acquiring supervision for guiding the alignment. To the best of our knowledge, few method in the literature can align multiple social networks without supervision. In this article, we propose to study the problem of unsupervised multiple social network alignment. To address this problem, we propose a novel unsupervised model of joint Matrix factorization with a diagonal Cone under orthogonal Constraint, referred to as MC 2 . Its core idea is to embed and align multiple social networks in the common subspace via an unsupervised approach. Specifically, in MC 2 model, we first design a matrix optimization to infer the common subspace from different social networks. To address the nonconvex optimization, we then design an efficient alternating algorithm by leveraging its inherent functional property. Through extensive experiments on real-world datasets, we demonstrate that the proposed MC 2 model significantly outperforms the state-of-the-art methods.

Social network alignment, aligning different social networks on their common users, is receiving dramatic attentions from both academic and industry. All existing studies consider the social network to be static and neglect its inherent dynamics. In fact, the dynamics of social networks contain the discriminative pattern of an individual, which can be leveraged to facilitate social network alignment. Hence, we for the first time propose to study the problem of aligning dynamic social networks. Towards this end, we propose a novel Dynamic Graph autoencoder based dynamic social network Alignment approach, referred to as DGA, unfolding the fruitful dynamics of social networks for user alignment. However, it faces challenges in both modeling and optimization: (1) To model the intra-network dynamics, we design a novel dynamic graph autoencoder to learn user embeddings with complex network dynamics. (2) To model the inter-network alignment, we design a unified optimization framework over proposed dynamic graph autoencoders, constructing a common subspace for user alignment across different networks. (3) To address this optimization problem, we design an effective alternating algorithm with solid theoretical guarantees. We conduct extensive experiments on real-world datasets and show that the proposed approach substantially outperforms the state-of-the-art methods.

Network alignment aims to discover nodes in different networks belonging to the same identity. In recent years, the network alignment problem has aroused significant attentions in both industry and academia. However, the continuous exploding of network data brings two challenges in solving the network alignment problem, i.e., large network scale and scarce labeled data. To bridge this gap, in this paper we propose a novel approach termed asMulti-granularItyNetwork alIgnment based on coNtrastive learninG(MINING). Specifically, in MINING, we first design multi-granularity alignment framework to solve the issue of large network scale. Then, we design intra- and inter-network contrastive learning to solve the issue of scarce labeled data. Moreover, we provide theoretical proofs to demonstrate the effectiveness of MINING. Finally, we conduct extensive experiments on the benchmark datasets of Facebook-Twitter, AMiner-LinkedIn and DBpedia$_{\text{ZH}}$-DBpedia$_{\text{EN}}$, and results show that MINING can averagely achieve 15.93% higher$\operatorname{Hits@}k$and 14.82% higher$\operatorname{MRR@}k$compared with the state-of-the-art methods.

Recently, aligning users among different social networks has received significant attention. However, most of the existing studies do not consider users' behavior information during the aligning procedure and thus still suffer from poor learning performance. In fact, we observe that social network alignment and user behavior analysis can benefit from each other. Motivated by such an observation, we propose to jointly study the social network alignment and user behavior analysis problem in this paper. We design a novel framework named BANANA-RGB. In this framework, to capture users' multi-scale behavior information in each social network, we train a variant of the hierarchical periodic memory network with personalized memorization. To leverage behavior analysis for social network alignment, we design a tensor fusion network-based alignment component to improve the performance. To further leverage social network alignment for behavior analysis, we design a gating-based cross-network behavior fusion component to integrate users' behavior information in different social networks based on the alignment result. We iteratively train the above two components to make the two tasks benefit from each other. Extensive experiments on real-world datasets demonstrate that our proposed approach outperforms the state-of-the-art methods.

Social network alignment, which aims to uncover the correspondence across different social networks, shows fundamental importance in a wide spectrum of applications such as cross-domain recommendation and information propagation. In the literature, the vast majority of the existing studies focus on the social network alignment at user level. In practice, the user-level alignment usually relies on abundant personal information and high-quality supervision, which is expensive and even impossible in the real-world scenario. Alternatively, we propose to study the problem of social group alignment across different social networks, focusing on the interests of social groups rather than personal information. However, social group alignment is non-trivial and faces significant challenges in both (i) feature inconsistency across different social networks and (ii) group discovery within a social network. To bridge this gap, we present a novel GroupAligner , a deep reinforcement learning with domain adaptation for social group alignment. In GroupAligner , to address the first issue, we propose the cycle domain adaptation approach with the Wasserstein distance to transfer the knowledge from the source social network, aligning the feature space of social networks in the distribution level. To address the second issue, we model the group discovery as a sequential decision process with reinforcement learning in which the policy is parameterized by a proposed p roximity-enhanced G raph N eural N etwork (pGNN) and a GNN-based discriminator to score the reward. Finally, we utilize pre-training and teacher forcing to stabilize the learning process of GroupAligner . Extensive experiments on several real-world datasets are conducted to evaluate GroupAligner , and experimental results show that GroupAligner outperforms the alternative methods for social group alignment.

Graph representation learning received increasing attentions in recent years. Most of the existing methods ignore the complexity of the graph structures and restrict graphs in a single constant-curvature representation space, which is only suitable to particular kinds of graph structure indeed. Additionally, these methods follow the supervised or semi-supervised learning paradigm, and thereby notably limit their deployment on the unlabeled graphs in real applications. To address these aforementioned limitations, we take the first attempt to study the self-supervised graph representation learning in the mixed-curvature spaces. In this paper, we present a novel Self-Supervised Mixed-Curvature Graph Neural Network (SelfMGNN). To capture the complex graph structures, we construct a mixed-curvature space via the Cartesian product of multiple Riemannian component spaces, and design hierarchical attention mechanisms for learning and fusing graph representations across these component spaces. To enable the self-supervised learning, we propose a novel dual contrastive approach. The constructed mixed-curvature space actually provides multiple Riemannian views for the contrastive learning. We introduce a Riemannian projector to reveal these views, and utilize a well-designed Riemannian discriminator for the single-view and cross-view contrastive learning within and across the Riemannian views. Finally, extensive experiments show that SelfMGNN captures the complex graph structures and outperforms state-of-the-art baselines.

Representation learning on temporal graphs has drawn considerable research attention owing to its fundamental importance in a wide spectrum of real-world applications. Though a number of studies succeed in obtaining time-dependent representations, it still faces significant challenges. On the one hand, most of the existing methods restrict the embedding space with a certain curvature. However, the underlying geometry in fact shifts among the positive curvature hyperspherical, zero curvature Euclidean and negative curvature hyperbolic spaces in the evolvement over time. On the other hand, these methods usually require abundant labels to learn temporal representations, and thereby notably limit their wide use in the unlabeled graphs of the real applications. To bridge this gap, we make the first attempt to study the problem of self-supervised temporal graph representation learning in the general Riemannian space, supporting the time-varying curvature to shift among hyperspherical, Euclidean and hyperbolic spaces. In this paper, we present a novel self-supervised Riemannian graph neural network (SelfℛGNN). Specifically, we design a curvature-varying Riemannian GNN with a theoretically grounded time encoding, and formulate a functional curvature over time to model the evolvement shifting among the positive, zero and negative curvature spaces. To enable the self-supervised learning, we propose a novel reweighting self-contrastive approach, exploring the Riemannian space itself without augmentation, and propose an edge-based self-supervised curvature learning with the Ricci curvature. Extensive experiments show the superiority of SelfRGNN, and moreover, the case study shows the time-varying curvature of temporal graph in reality.

Knowledge graph embedding aims to learn representations of entities and relations in low-dimensional space. Recently, extensive studies combine the characteristics of knowledge graphs with different geometric spaces, including Euclidean space, complex space, hyperbolic space and others, which achieves significant progress in representation learning. However, existing methods are subject to at least one of the following limitations: 1) ignoring the uncertainty, 2) incapability of complex relation patterns. To address the above issues simultaneously, we propose a novel model named DiriE, which embeds entities as Dirichlet distributions and relations as multinomial distributions. DiriE employs Bayesian inference to measure the relations between entities and learns binary embeddings of knowledge graphs for modeling complex relation patterns. Additionally, we propose a two-step negative triple generation method that generates negative triples of both entities and relations. We conduct a solid theoretical analysis to demonstrate the effectiveness and robustness of our method, including the expressiveness of complex relation patterns and the ability to model uncertainty. Furthermore, extensive experiments show that our method outperforms state-of-the-art methods in link prediction on benchmark datasets.

In social networks, one of the most significant challenges is how to estimate the tweet popularity. Prior studies focus on leveraging different aspects of just a single tweet, while ignoring the impact of historical tweets. In this article, we propose to leverage such historical information and rethink the problem of tweet popularity estimation. From historical information, there are two important factors that can be extracted: (1) user reputation feature, which can represent coarse-grained level of tweet popularity and (2) tweet related features, which can represent fine-grained level of tweet popularity. To incorporate these two factors from historical information, we design a novel deep neural architecture, a Bi-layered LSTM for tweet popUlarity Estimation, called DeepBlue. Specifically, we first propose a user-reputation aware mechanism to combine coarse-grained and fine-grained level estimation into a united LSTM model. We also design a content attention mechanism to consider different impacts of historical tweets in terms of content similarity. We then propose a time aware mechanism to address the time interval irregularity issue. Finally, we apply the Poisson regression model to obtain the overall loss for tweet popularity estimation. Extensive experiments demonstrate the superiority of our proposed approach to other state-of-the-arts in terms of MAE and SRC.

Learning representations for graphs plays a critical role in a wide spectrum of downstream applications. In this paper, we summarize the limitations of the prior works in three folds: representation space, modeling dynamics and modeling uncertainty. To bridge this gap, we propose to learn dynamic graph representations in hyperbolic space, for the first time, which aims to infer stochastic node representations. Working with hyperbolic space, we present a novel Hyperbolic Variational Graph Neural Network, referred to as HVGNN. In particular, to model the dynamics, we introduce a Temporal GNN (TGNN) based on a theoretically grounded time encoding approach. To model the uncertainty, we devise a hyperbolic graph variational autoencoder built upon the proposed TGNN to generate stochastic node representations of hyperbolic normal distributions. Furthermore, we introduce a reparameterisable sampling algorithm for the hyperbolic normal distribution to enable the gradient-based learning of HVGNN. Extensive experiments show that HVGNN outperforms state-of-the-art baselines on real-world datasets.

Recently, reconciling social networks, identifying the accounts belonging to the same individual across social networks, receives significant attention from both academic and industry. Most of the existing studies have limitations in the following three aspects: multiplicity, comprehensiveness and robustness. To address these limitations, we rethink this problem and, for the first time, robustly and comprehensively reconcile multiple social networks. In this paper, we propose two frameworks, MASTER and MASTER+, i.e., across Multiple social networks, integrate Attribute and STructure Embedding for Reconciliation. In MASTER, we first design a novel Constrained Dual Embedding model, simultaneously embedding and reconciling multiple social networks, to formulate this problem into a unified optimization. To address this optimization, we then design an effective NS-Alternating algorithm and prove it converges to KKT points. To further speed up MASTER, we propose a scalable framework, namely MASTER+. The core idea is to group accounts into clusters and then perform MASTER in each cluster in parallel. Specifically, we design an efficient Augmented Pre-Embedding model and Balance-aware Fuzzy Clustering algorithm for the high efficiency and the high accuracy. Extensive experiments demonstrate that both MASTER and MASTER+ outperform the state-of-the-art approaches. Moreover, MASTER+ inherits the effectiveness of MASTER and enjoys higher efficiency.

Graph Neural Networks (GNNs) have been widely applied to fraud detection problems in recent years, revealing the suspiciousness of nodes by aggregating their neighborhood information via different relations. However, few prior works have noticed the camouflage behavior of fraudsters, which could hamper the performance of GNN-based fraud detectors during the aggregation process. In this paper, we introduce two types of camouflages based on recent empirical studies, i.e., the feature camouflage and the relation camouflage. Existing GNNs have not addressed these two camouflages, which results in their poor performance in fraud detection problems. Alternatively, we propose a new model named CAmouflage-REsistant GNN (CARE-GNN), to enhance the GNN aggregation process with three unique modules against camouflages. Concretely, we first devise a label-aware similarity measure to find informative neighboring nodes. Then, we leverage reinforcement learning (RL) to find the optimal amounts of neighbors to be selected. Finally, the selected neighbors across different relations are aggregated together. Comprehensive experiments on two real-world fraud datasets demonstrate the effectiveness of the RL algorithm. The proposed CARE-GNN also outperforms state-of-the-art GNNs and GNN-based fraud detectors. We integrate all GNN-based fraud detectors as an opensource toolbox https://github.com/safe-graph/DGFraud. The CARE-GNN code and datasets are available at https://github.com/YingtongDou/CARE-GNN.

With the growing prosperity and diversity of social networks, more and more users participate in multiple social networks to enjoy their diverse services. Users can create different user identities in different social networks, but most networks are independent of each other. Hence, a fundamental question arises: can we align user identities across social networks? Related work mostly focuses on Euclidean geometry to learn representation vectors of social networks. However, motivated by recent advances in geometry representation learning, we find that hyperbolic geometry shows the advantage of expressing network hierarchical structure, while Euclidean geometry doesn't. Thus, in this paper, we first introduce the connection between hyperbolic space and social networks. Then we propose a novel hyperbolic geometry representation learning model for user identity linkage across social networks, which is called “HUIL”. Finally, we conduct comprehensive experiments on real-world datasets and verify the superiority of HUIL for user identity linkage.

Social network alignment shows fundamental importance in a wide spectrum of applications. To the best of our knowledge, existing studies mainly focus on network alignment at the individual user level, requiring abundant common information between shared individual users. For the networks that cannot meet such requirements, social community structures actually provide complementary and critical information at a slightly coarse-grained level, alignment of which will provide additional information for user alignment. In turn, user alignment also reveals more clues for community alignment. Hence, in this paper, we introduce the problem of joint social network alignment, which aims to align users and communities across social networks simultaneously. Key challenges lie in that (1) how to learn the representations of both users and communities, and (2) how to make user alignment and community alignment benefit from each other. To address these challenges, we first elaborate on the characteristics of real-world networks with the notion of δ-hyperbolicity, and show the superiority of hyperbolic space for representing social networks. Then, we present a novel hyperbolic embedding approach for the joint social network alignment, referred to as Perfect, in a unified optimization. Extensive experiments on real-world datasets show the superiority of Perfect in both user alignment and community alignment.

Recently, aligning users among different social networks has received significant attention. However, most of the existing studies do not consider users’ behavior information during the aligning procedure and thus still suffer from the poor learning performance. In fact, we observe that social network alignment and behavior analysis can benefit from each other. Motivated by such an observation, we propose to jointly study the social network alignment problem and user behavior analysis problem. We design a novel end-to-end framework named BANANA. In this framework, to leverage behavior analysis for social network alignment at the distribution level, we design an earth mover’s distance based alignment model to fuse users’ behavior information for more comprehensive user representations. To further leverage social network alignment for behavior analysis, in turn, we design a temporal graph neural network model to fuse behavior information in different social networks based on the alignment result. Two models above can work together in an end-to-end manner. Through extensive experiments on real-world datasets, we demonstrate that our proposed approach outperforms the state-of-the-art methods in the social network alignment task and the user behavior analysis task, respectively.

Social network alignment, identifying social accounts of the same individual across different social networks, shows fundamental importance across a wide spectrum of applications. Individuals more often than not join in multiple social networks and it is in fact intractable or even impossible to acquiring supervision for guiding the alignment. However, to the best of our knowledge, none of existing methods can align multiple social networks without supervision. In this paper, we propose to study the problem of unsupervised multiple social network alignment. To address this problem, we propose a novel unsupervised model of Matrix factorization with diagonal Cone under orthogonal Constraint, referred to as MC2. Its core idea is to embed and align multiple social networks in the common subspace via an unsupervised approach. Specifically, in MC2model, we first design a matrix optimization to infer the common subspace from different social networks. To address the nonconvex optimization, we then design an efficient alternating algorithm by leveraging its inherent functional property. Through extensive experiments on real-world datasets, we demonstrate that the proposed MC2model significantly outperforms the state-of-the-art methods.

Social network alignment, aligning different social networks on their common users, is receiving dramatic attention from both academic and industry. All existing studies consider the social network to be static and neglect its inherent dynamics. In fact, the dynamics of social networks contain the discriminative pattern of an individual, which can be leveraged to facilitate social network alignment. Hence, we for the first time propose to study the problem of aligning dynamic social networks. Towards this end, we propose a novel Dynamic social Network Alignment (DNA) framework, a unified optimization approach over deep neural architectures, to unfold the fruitful dynamics to perform alignment. However, it faces tremendous challenges in both modeling and optimization: (1) To model the intra-network dynamics, we explore the local dynamics of the latent pattern in friending evolvement and the global consistency of the representation similarity with neighbors. We design a novel deep neural architecture to obtain the dual embedding capturing local dynamics and global consistency for each user. (2) To model the inter-network alignment, we exploit the underlying identity of an individual from the dual embedding in each dynamic social network. We design a unified optimization approach interplaying proposed deep neural architectures to construct a common subspace of identity embeddings. (3) To address this optimization problem, we design an effective alternating algorithm with solid theoretical guarantees. We conduct extensive experiments on real-world datasets and show that the proposed DNA framework substantially outperforms the state-of-the-art methods.

In social networks, one of the most significant challenges is how to estimate the tweet popularity. Prior studies about this problem focus on leveraging different aspects of just a single tweet, while ignoring the impact of historical tweets. In this paper, we propose to leverage such historical information and rethink the problem of tweet popularity estimation. From historical information, there are two important factors that can be extracted: (1) user reputation feature, which can represent coarse-grained level of tweet popularity; (2) tweet related features, which can represent fine-grained level of tweet popularity. To incorporate two factors from historical information, we design a novel deep neural architecture, a Bi-layered LSTM for tweet popularity Estimation, called DeepBlue. Specifically, we first propose a user-reputation aware mechanism to combine coarse-grained and fine-grained level estimation into a unified LSTM model. We then propose a time aware mechanism to address the time interval irregularity issue in standard LSTM. Finally, we apply the Poisson regression model to obtain the overall loss for tweet popularity estimation. Extensive experiments demonstrate the superiority of our proposed approach to other state-of-the-arts in terms of MAE and SRC.

Recently, reconciling social networks receives significant attention. Most of the existing studies have limitations in the following three aspects: multiplicity, comprehensiveness and robustness. To address these three limitations, we rethink this problem and propose the MASTER framework, i.e., across Multiple social networks, integrate Attribute and STructure Embedding for Reconciliation. In this framework, we first design a novel Constrained Dual Embedding model by simultaneously embedding and reconciling multiple social networks to formulate our problem into a unified optimization. To address this optimization, we then design an effective algorithm called NS-Alternating. We also prove that this algorithm converges to KKT points. Through extensive experiments on real-world datasets, we demonstrate that MASTER outperforms the state-of-the-art approaches.