Papers for

social network engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Theory based method finds true links in noisy bipartite networks

Theory-Driven Network Backbones for Bipartite Projections

Abstract: Collecting data, including network data, is subject to measurement error. Network backboning is the process of statistically validating each edge in a network to estimate the probability that the edge is born of noisy measurements. The current backboning literature provides approaches in two classes: structural and statistical. The classes differ in many respects, but they share one commonality: the test used to determine whether to filter out noisy edges is data-agnostic; it does not take into account what the network is representing. However, the nodes and edges of all non-synthetic networks correspond to specific real-world entities, whose dynamics determine how the edge-generating process operates. In this paper, we propose the first in a new class of network backboning algorithms: a theory-driven backboning approach that allows us to encode known dynamics into the backboning process. The resulting backbone embeds the encoded theory and produces a network compatible with it, rather than one that obeys a data-agnostic network process, as in the structural and statistical backboning classes. We specifically focus on the case of projecting and backboning a bipartite structure. We do so by allowing users to specify an Agent-Based Model for the two types of agents (nodes) in the network and by performing Simulation-Based Inference to fit the observed bipartite structure and, as a result, reconstruct the true relationships between the two classes of agents. We test our framework both on synthetic data -- where we have perfect information about the edge-generating process -- and in a case study using archaeological data on amphorae retrieved from different archaeological sites. Our approach improves latent-edge recovery over conventional backboning methods in synthetic experiments and reveals interpretable archaeological patterns despite imperfect model fit.

Thu 12 NovSocial and Information NetworksDatabases
The gist
Measuring connections in networks often includes errors that make it hard to tell real relationships from noise. The authors propose a new way to clean up these networks by using knowledge about how the connections should form based on a theory of the agents involved. They focus on networks with two types of nodes and use simulations to match the observed data to the theory, finding better and more meaningful links. They tested this idea with both pretend data and archaeological findings, showing it works better than usual methods.
Open → 2611.16692v1

GPU method speeds training of massive graph neural networks fourfold

GARDEN: Efficient GPU-Accelerated Billion-Scale GNN Training via Caching-Sampling-Batching Co-Design

Abstract: Graph Neural Networks (GNNs) have shown impressive performance in diverse tasks such as social network analysis and recommendation systems. However, scaling their training to billion-edge graphs is hindered by the memory wall: GPU memory capacity falls short of the massive storage requirements for node features and topology. Sampling-based GNN training frameworks mitigate this by streaming subgraphs from CPU to GPU, but they incur prohibitive PCIe data transfers and non-coalesced memory accesses, resulting in bandwidth underutilization and low compute efficiency. We propose GARDEN, a GPU-accelerated sampling-based system that co-designs caching, sampling, and batching to eliminate these bottlenecks. GARDEN introduces three key innovations: (1) an Adaptive High-Fidelity Cache Allocator (AHFCA) that combines offline reuse profiling and online hotness tracking to dynamically cache features and adjacency lists within a fixed GPU memory budget, avoiding static allocation waste; (2) a Grouping-based Parallel Sampler that reorders stochastic neighborhood accesses(GPS) to maximize warp occupancy and hide latency on power-law graphs; and (3) a Super-batch Degree Classifier(SDC) that fuses mini-batches into degree-homogeneous groups, enabling cache-friendly coalesced transfers and high GPU utilization. Evaluations on real-world billion-scale graphs demonstrate that GARDEN achieves 4.54x, 1.27x, and 2.97x end-to-end training speedups over DGL-UVA, DUCATI, and FastGL, respectively, while maintaining model convergence and accuracy.

Sun 8 NovDistributed, Parallel, and Cluster Computing
The gist
Training graph neural networks on very large graphs is hard because GPUs cannot hold all the required data at once. The authors developed a new system called GARDEN that smartly stores frequently used data in GPU memory, orders data sampling to speed up GPU processing, and groups training batches to make data transfers more efficient. This system speeds up training by up to over four times compared to previous methods, without losing accuracy. Their approach works on real-world graphs with billions of connections.
Open → 2611.11043v1

MambaTG improves future link prediction on changing networks

MambaTG: Candidate-Aware State Space Modeling for Future Link Prediction on Temporal Graphs

Abstract: Future link prediction on temporal graphs involves both repeated interactions between previously connected node pairs and first-time interactions between pairs with no prior interaction. While repeated-edge prediction can exploit direct pairwise evidence, unseen-edge prediction must generalize beyond historical recurrence. Existing temporal graph models often exploit signals tied to recurring interactions or historical overlap, which are highly informative for repeated edges but become limited or unavailable for unseen edges, contributing to substantial performance degradation on unseen-edge prediction. Based on this observation, we identify two complementary signals for modeling sequential dynamics beyond historical recurrence: (1) historical-sequence evolution, which captures dependencies among the source node's chronologically ordered interactions, and (2) candidate--history compatibility, which captures how well a candidate fits the source node's evolving history. Based on the decomposition, we propose MambaTG, a candidate-aware Mamba-based framework that jointly models these two signals. Mamba provides a natural mechanism for this design: its selective recurrence captures the evolution of ordered interaction histories, while its input-dependent state transitions allow the history state to adapt to different candidate inputs. Extensive experiments on 13 temporal graph datasets against 13 representative baselines show that MambaTG achieves strong and consistent performance across both repeated and unseen edges while remaining computationally efficient.

Thu 5 NovMachine Learning
The gist
Predicting new and repeated interactions in networks that change over time is challenging because methods often do well only if the interaction has happened before. The authors noticed that existing models rely heavily on past repeated patterns, which hurts their ability to predict new connections between nodes. They propose MambaTG, a method that learns how a node's interaction history evolves and how well potential new connections fit into this evolving context. Their approach works well for both repeated and unseen connections and runs efficiently across many datasets.
Open → 2611.07569v1

Graph neural networks certified to resist training data attacks

Certifying Graph Neural Networks Against Label and Structure Poisoning

Abstract: Robust machine learning for graph-structured data has made significant progress against test-time attacks, yet certified robustness to poisoning - where adversaries manipulate the training data - remains largely underexplored. For image data, state-of-the-art poisoning certificates rely on partitioning-and-aggregation schemes. However, we show that these methods fail when applied in the graph domain due to the inherent label and structure sparsity found in common graph datasets, making effective graph-partitioning difficult. To address this challenge, we propose a novel semi-supervised learning framework called deep Self-Training Graph Partition Aggregation (ST-GPA), which enriches each graph partition with informative pseudo-labels and synthetic edges, enabling effective certification against node-label and graph-structure poisoning under sparse conditions. Our method is architecture-agnostic, scales to large numbers of partitions, and consistently and significantly improves robustness guarantees against both label and structure poisoning across multiple benchmarks, while maintaining strong clean accuracy. Overall, our results establish a promising direction for certifiably robust learning on graph-structured data against poisoning under sparse conditions.

Mon 2 NovMachine Learning
The gist
Machine learning models that work on graph data can be tricked when someone changes the training data they learn from. The authors found that methods used for images don’t work well for graphs because graphs have fewer labels and connections to group together. They created a new technique called ST-GPA that improves the way these graphs are divided and labeled during training. This helps the models stay accurate while becoming more reliable against attackers who try to mess with the training data.
Open → 2611.03350v1

Triadic closure preserves local patterns and boosts clustering in random graphs

Local Convergence of Triadic Closures of Sparse Random Graphs

Abstract: Triadic closure is a natural mechanism for modeling the clustering phenomenon observed in many real-world networks. Given a possibly random undirected graph $H$, we consider pairs of non-adjacent vertices that have a common neighbor. Conditional on $H$, each such pair is joined by an edge independently and simultaneously, with a probability depending on the degrees of its endpoints and on the number of their common neighbors. The resulting graph is called a triadic closure of $H$. We study the effect of this operation on local convergence. More precisely, we prove that if a sequence of potentially random finite undirected graphs of $\left( H_n \right)_{n \in \mathbb{N}}$ converges locally in probability to a rooted graph $H^*$, then the corresponding sequence of triadic closures converges locally in probability to the same triadic closure of $H^*$. As a consequence, we obtain a general limit theorem for the clustering coefficients of triadic closures. In particular, we show that the triadic closures can have a strictly positive limiting clustering coefficients even when the limiting clustering coefficients of the parent graph sequence is zero. Finally, we apply our results to several classical sparse random graph models including Erdős-Rényi, configuration, preferential attachment models and compute the limiting clustering coefficients of their triadic closures.

Thu 29 OctDiscrete Mathematics
The gist
Clustering shows how friends of friends often become friends too, which happens a lot in social networks. The authors study a process called triadic closure, where pairs of nodes with a shared neighbor get connected with some chance, based on their connections. They prove that if a sequence of graphs behaves a certain way locally, then their triadic closures behave similarly, keeping the local structure intact. They also show that even if the original graphs have low clustering, their triadic closures can have positive clustering. The theory applies to popular random graph models like Erdős-Rényi and preferential attachment.
Open → 2610.39535v1

Concorde improves link prediction in sparse and complex graphs

Concorde: Geometry-Aware Link Prediction via Decoupled Energy Minimization

Abstract: Link prediction remains difficult in sparse graphs, where diffusion heuristics lack connectivity and geometric methods suffer spectral instability when coupling learned representations with diffusion operators. We introduce Concorde, an energy-based framework that resolves this by decomposing link likelihood into three structurally decoupled branches: (i) a parameter-free spectral anchor that establishes permutation-invariant topological stability; (ii) a mixed-curvature residual on a learnable $\mathbb{H}^{d_h}_{c_h} \times \mathbb{S}^{d_s}_{c_s}$ product manifold, regularized by a feature-aware Ollivier-Ricci curvature proxy; and (iii) a continuous vector field on the tangent bundle of hyperbolic space for non-local structural alignment across topological gaps. The branches are fused via learned gating and trained with an N-pair ranking loss aligned with retrieval-style evaluation. Across five benchmarks spanning sparse, dense, featureless, and attributed regimes, Concorde establishes state-of-the-art early retrieval precision, nearly doubling P@10% over leading baselines in sparse settings.

Mon 26 OctMachine LearningArtificial Intelligence
The gist
Link prediction helps guess which connections might form in networks, but this is hard when there isn’t much data or the network structure is complex. The authors introduce Concorde, a new approach that breaks down the problem into three simpler parts using geometry and graph properties to better predict links. One part looks at stable patterns in the network, another learns complex curved spaces to capture structure, and the last aligns distant connections. Tested on various datasets, Concorde shows much better precision especially in sparse networks.
Open → 2610.36204v1

Graph query processing speeds up by focused distributed partitioning

Scaling Graph Query Processing: Focused Exploration on Partitions Using Load Balancing

Abstract: The focus of this paper is on query processing and not search (approximate or exact). The goal is to find all or k answers and the expressiveness of a query (as opposed to a search expression which is typically simpler) is considered important. Although SQL query processing has matured over the last several decades, query processing over graph data has not received the same attention. Only recently, systems, such as Neo4J, and others have started using graphs for data representation on a large scale. Their approaches and algorithms remain proprietary. In this paper, we address the problem of answering graph queries and their efficient processing on arbitrary-sized graphs. We propose the partitioning of graphs and the use of the distributed paradigm to achieve efficiency and scalability. Our approach takes a subgraph as query input including wild cards and comparison operations. Our partitioned approach leverages focused exploration and distributed processing to achieve the desired parallelism and improve the response time. We also present heuristics to reduce the number of partitions loaded for query processing. We present our partitioning algorithm, distributed processing architecture used, and load balancing for computing query answers. We establish the correctness of the approach in the presence of partitions, compare heuristics for load balancing, and extensive experimental results over large synthetic and real-world graph data sets.

Fri 23 OctDatabasesDistributed, Parallel, and Cluster ComputingInformation Retrieval
The gist
Finding answers in big network-like data sets can be slow and tricky. The authors offer a way to split these big networks into smaller pieces that computers can explore in parallel. Their method smartly decides where to look first to avoid wasting time and balances the work across machines. This helps get query answers faster, even on very large and complex graphs. They tested their approach using both real and made-up large network data.
Open → 2610.32015v1

Graph filters improve stability when generating data on networks

Stabilizing Filters for Graph Signal Generation

Abstract: Generating graph signals is an important task in machine learning, and incorporating the underlying graph into a generative model enables structurally-informed distribution modeling. However, said graph is often noisy or imperfectly estimated, and structural errors can affect the generative process and the resulting signal distribution. While recent work has established stability guarantees for graph neural ordinary differential equations, the robustness of graph-aware reference dynamics, as used in topological Schrödinger bridge models, remains largely unexplored. Here, we investigate the structural stability of continuous-time generative models whose dynamics combine a graph filter with a learned graph neural network. We first derive a Wasserstein stability bound that quantifies the effect of graph perturbations on the generated signal distributions. Informed by this analysis, we then propose a principled framework for designing graph filters that balance structural stability with induced signal smoothing. We characterize the optimal filter design and provide an explicit family of polynomial filters with provable stability guarantees. Experiments on synthetic graphs and real-world fMRI signals support our theoretical findings, illustrating the enhanced structural stability of the proposed filters while preserving generative performance.

Tue 20 OctMachine Learning
The gist
Generating signals that sit on networks, like social connections or brain regions, can be tricky because the network itself might have errors. The authors studied how small mistakes in the network affect the data generation process and found a way to measure this impact precisely. They then designed special filters that make the generation more stable despite those errors, all while keeping the generated signals meaningful. Tests on fake and brain data showed these filters work well at balancing stability and signal quality.
Open → 2610.28318v1

Local privacy method counts small network patterns with optimal accuracy

Subgraph Counting with Local Node Differential Privacy

Abstract: We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introduced model that enforces strong privacy guarantees in analyses of distributed social networks. We design a noninteractive $(\varepsilon,0)$-LNDP algorithm that, given any public $k$-node template graph $H$, counts occurrences of $H$ in a sensitive undirected $n$-node graph with additive error $O(n^{k-\frac{1}{2}}/\varepsilon^{k-1})$, for any constant $k$. We complement this algorithm with a lower bound showing that every noninteractive $(\varepsilon,δ)$-LNDP algorithm for counting copies of any $k$-node template graph with maximum degree greater than $1$ must have error $Ω(n^{k - \frac{1}{2}})$. Thus, our algorithm achieves optimal error for counting constant-size subgraphs, up to $\mathrm{poly}(1/\varepsilon)$ factors. Our results substantially expand the types of network statistics known to be approximable under LNDP: prior work considered only functions of the degree distribution. In addition, our lower bound yields the first known $\mathrm{poly}(n)$ gap between central and local node differential privacy when accuracy is required for all input graphs. Previous separations either only involved $\mathrm{poly}(1/\varepsilon)$ factors or only applied to promise problems.

Thu 15 OctData Structures and AlgorithmsCryptography and Security
The gist
Counting small patterns in social networks helps understand connections, but sharing this data can threaten privacy. The authors developed a new method that protects individual users' connections while still counting these patterns accurately. They prove their method is about as good as possible and show that protecting privacy this way is harder than traditional methods. This improves on previous work which only handled simpler statistics about networks.
Open → 2610.22278v1

Voter model with opinion graph limits influence based on opinion proximity

The Voter Model with Opinion Graph

Abstract: We study the \emph{voter model with opinion graph}, a generalization of the standard (pull) voter model that adds a notion of bounded confidence. In this process, we consider a finite set $A$ of $n$ agents. Each agent $u \in A$ has an opinion $x_u \in O$, where we model opinions as vertices in an undirected opinion graph $G = (O,E)$ with $|O|=q$. In each step, an agent $u$ interacts with another agent $v \in A$. In contrast to classical voting, $u$ adopts the opinion $x_v$ if and only if $x_v$ and $x_u$ are neighbors in $G$. The process is stable once all remaining opinions are an independent set in $G$. We analyze two variants of the process: the ordinary EdgeVOG process, which samples a pair of interacting agents uniformly at random from all possible pairs, and the productive EdgeVOG process, which samples only pairs with neighboring opinions in $G$. We show the following: - For every opinion graph and every initial configuration, ordinary EdgeVOG stabilizes within $O(n^2\log n)$ steps in expectation and with high probability. The expectation bound is asymptotically tight. For the productive EdgeVOG process, the expected stabilization time is exactly the initial number of compatible agent pairs, while $O(n^2\log n)$ steps suffice with high probability. - An opinion $i$ with initial support $s_i$ survives with probability at least $p_i:=s_i/(s_i+\sum_{j\in N(i)}s_j)$. Further, let $μ= \sum_{i \in O} p_i$, then we show the probability that less than $(1-δ)μ$ opinions survive is at most $\exp(-δ^2μ/(2(Δ^2+1)))$ for every $0\leqδ\leq1$. -If $G$ has maximum degree $Δ$ and every opinion initially has support at most $\hat{s}$, then no opinion ever acquires more than $\tilde{O}(\min\{n,Δ^6\hat{s}\})$ agents with high probability. This yields near-linear stabilization bounds for productive EdgeVOG for a large class of configurations.

Mon 12 OctComputer Science and Game TheoryDistributed, Parallel, and Cluster Computing
The gist
This work studies how opinions spread among a group of people when they only influence each other if their opinions are similar. The authors model opinions as points in a network where connections mean opinions are close enough to influence. They analyze how long it takes for opinions to stop changing and how likely each opinion is to survive over time. Their findings show that the process stabilizes quickly and predict how opinions grow or disappear based on their initial popularity and connections.
Open → 2610.16684v1

Stochastic agents simulate people in grassroots social platform apps

sGLP: Specifying Stochastic Agents that Simulate People

Abstract: Grassroots platforms are designed to be owned, operated and governed by their participants, and thus are constituted from person-to-person smartphone apps that run on participants' smartphones. A grassroots app is specified using a grassroots social contract, which is compiled through an abstraction cascade into a volition-guarded Grassroots Logic Program (vGLP), a multiagent concurrent logic programming language. A vGLP program in turn specifies a smartphone UI via which people express their volitions and thus control the app. Prudence dictates large-scale evaluation and testing of grassroots platforms prior to deployment, but using the many people needed to do that is a contradiction in terms. Hence another solution is needed. Here, we present stochastic GLP (sGLP), designed to allow grassroots platforms to be simulated at scale from the vGLP programs that deploy them, with stochastic agents in place of people. sGLP is GLP with a rate extension for specifying stochastic behaviour. A stochastic agent is an sGLP program replacing both the vGLP UI and the person behind it. It is typed by the dual of the interactive type of the UI and specifies a stochastic profile of a person's behaviour. We demonstrate sGLP on the grassroots social graph, with a population of men and women drawn from four stochastic profiles --- homophile or indifferent, wary or sociable --- and on grassroots currencies, with four profiles --- spenders or savers, cautious or generous --- and report what the mix of profiles does to the social graph that forms and to the currencies that circulate. We prove that every run of a vGLP program in which sGLP agents replace the UI and the people behind it is a vGLP run. We implemented sGLP in GLP by Gillespie's method, and ran reproducible simulations with it.

Sat 10 OctMultiagent SystemsDistributed, Parallel, and Cluster ComputingHuman-Computer Interaction
The gist
Grassroots platforms are smartphone apps run and governed by people using social contracts. Testing these platforms at large scale is hard because you would need many real people to do it. The authors created sGLP, a tool that simulates people with different behavior styles inside these apps, letting developers test how the system behaves. Their simulations used different social and currency behavior profiles, showing how these affect the social connections and money flow. They also proved mathematically that these simulations follow the platform’s original logic precisely.
Open → 2610.14738v1

Scalable method generates large graphs with realistic community structure

Scalable Hierarchical Graph Generation via Soft Community Structure

Abstract: Generating large attributed graphs requires reproducing the topology, generating attributes jointly with the structure, and remaining scalable. Many real-world graphs exist as a single large graph, so a generative model has to generalize from the one graph it is fit on, without independent samples. We present Schema, which recursively decomposes a reference graph into a hierarchy of soft communities, assigning each node a membership distribution. Generation is then split into three stages, each trained independently: (1) synthesizing node attributes conditioned on soft memberships, (2) generating intra-community edges from local structural context, and (3) modeling inter-community connections over bridge nodes whose membership mass is distributed across several communities. No stage forms the full adjacency matrix, and each stage operates on a subgraph bounded by the community size. We also introduce an evaluation protocol that covers structural fidelity, memorization, downstream utility, and scalability. On four real-world attributed graphs, Schema recovers the balance between local and long-range structure more closely than any other model that generates attributes, while reproducing only a small fraction of the reference edges. It retains the downstream accuracy of the reference graph without raising it artificially above that level. Baselines that match its structural fidelity memorize the reference, while those with higher downstream accuracy either exceed the reference accuracy or fail to complete on the larger graphs. We measure scalability on six additional graphs with up to 10 million nodes.

Thu 8 OctMachine LearningArtificial Intelligence
The gist
Creating big networks with lots of details is tough because you usually have only one big example to learn from. The authors introduce Schema, a way to break down a big network into smaller overlapping groups, then generate the network step-by-step using these groups. This method makes it easier to produce large realistic networks that keep important patterns without simply copying the original. Their method works well on real networks and scales up to networks with millions of nodes.
Open → 2610.12163v1

Byzantine causal reliable broadcast with constant message overhead

Byzantine Causal Reliable Broadcast with Constant Metadata Overhead

Abstract: Asynchronous Byzantine Reliable Broadcast (BRB) is a fundamental primitive that guarantees agreement and validity in distributed systems subject to Byzantine faults, but it lacks ordering guarantees. Causal message ordering is important for many applications such as blockchain and social networking. Existing solutions for Byzantine Causal Reliable Broadcast (BCRB) have several drawbacks. Such protocols typically append vector clocks or dependency barriers to application messages, resulting in a metadata overhead that scales linearly with $n$, the number of processes in the system. In this paper, we propose the first optimal message overhead BCRB algorithm that guarantees safety. We do this by re-engineering Bracha's BRB algorithm with relatively small but critical modifications, and prove that our algorithm solves BCRB with optimal message metadata. The algorithm achieves constant-size $\mathcal{O}(1)$ message metadata overhead and $\mathcal{O}(n^2)$ messages, resulting in $\mathcal{O}(n^2)$ communication word complexity. This is as against $\mathcal{O}(n^3)$ communication word complexity of existing protocols. The algorithm tolerates $f < n/3$ Byzantine processes, which is the well-known optimal resilience bound, and uses four phases.

Tue 29 SeptDistributed, Parallel, and Cluster ComputingData Structures and Algorithms
The gist
Sending messages reliably in a system where some parts might behave badly is tricky, especially when messages need to follow a certain order. The authors improved how these messages are sent so the extra information attached to each message stays the same size, no matter how big the system grows. Their solution uses smarter steps to keep messages safe and ordered without making them bigger over time. This approach also reduces the total communication cost compared to earlier methods.
Open → 2609.37913v1

Simple counts rival learned memory for predicting future links

Do Temporal Link Predictors Need Learned Memory? A Smoothed-Count Baseline with a Handful of Parameters

Abstract: Many temporal link predictors summarize past interactions through learned node representations. We examine whether simple counts of recurring interaction patterns can provide competitive predictions without learning these representations. We propose a temporal link predictor based on statistical language modelling. It pools transition and co-occurrence counts across sources to predict links that a source has never formed. We smooth sparse estimates using destination frequencies or Kneser-Ney continuation counts. A shared log-linear rule combines these estimates with popularity, source history, and recency, without node embeddings. In our main evaluation, the model achieves the highest MRR among the compared methods on 7 out of 16 datasets from TGB and TGB-Seq. It also outperforms EdgeBank and Base3 on all 16 datasets and the heuristic family on 14. These gains extend to datasets designed to limit repeated edges. With only 9--13 learned parameters, our model provides a simple and competitive baseline for evaluating future neural temporal link predictors.

Mon 28 SeptMachine LearningArtificial Intelligence
The gist
Predicting future connections between things that interact over time usually relies on complex methods that learn patterns from past interactions. This paper shows that just counting how often certain repeated interaction patterns occur, combined with some simple rules, can predict these future links just as well or better than many advanced methods. The authors created a model that uses these counts with only a handful of adjustable settings and found it works very well across a variety of datasets. This suggests that complicated learned memories might not always be necessary for good temporal link prediction.
Open → 2609.35364v1

Graph neural networks improve link prediction by addressing node role confusion

Edge-Level Automorphism in GNNs: A Quantitative Framework and Effective Designs For Link Prediction

Abstract: Graph Neural Networks (GNNs) are effective for learning node and link embeddings through permutation-equivariant aggregation. However, standard GNNs collapse automorphic nodes, i.e., those with identical structural roles (or orbits) into indistinguishable representations, leading to the node automorphism problem. This collapse limits their expressive power and degrades link prediction performance. Existing approaches to characterize GNN expressiveness rely primarily on Weisfeiler-Lehman (WL) analyses, but these methods are typically qualitative and often misaligned with empirical results. To address this gap, we begin by introducing a novel quantitative framework to assess GNN expressiveness for link prediction. We first formalize edge-level automorphism through edge orbits, which capture the set of structural role pairs for nodes that share a link. Then, we introduce the edge automorphism ratio (EAR), a scalar metric that quantifies a GNN's ability to distinguish links in a given graph. We empirically demonstrate that EAR correlates strongly with performance, validating its practical benefit. Building on this insight, we design EDGE-ORBIT EQUIVARIANT GRAPH NEURAL NETWORK (EO-GNN), a GNN architecture that addresses automorphism collapse while preserving equivariance and incurring minimal computational overhead. EO-GNN accomplishes this through two core designs combined with WL-based node hashes: (i) automorphism-aware dropouts and (ii) subgraph orbit-biased aggregation. Empirical evaluations on synthetic and real graphs show improvements of up to 42.36% and 28.44%, respectively, in predicting links in scenarios with high automorphism.

Mon 28 SeptMachine LearningComputer Science and Game Theory
The gist
Graph neural networks (GNNs) try to learn patterns in networks by looking at how nodes connect. But when different nodes have the same structural role, standard GNNs treat them as identical, which hurts their ability to predict links. The authors introduce a way to measure how well GNNs can tell these links apart using a new metric called edge automorphism ratio (EAR). They then build a new GNN design called EO-GNN that avoids confusing node roles, helping it predict links more accurately on both made-up and real networks.
Open → 2609.34729v1

Graph foundation model trained on web graph enables versatile tasks

Training Graph Foundation Models on The Web Graph

Abstract: We introduce Acacia, a graph foundation model, trained on the web graph. Acacia (i) supports arbitrary feature dimensionalities and semantics without additional training, (ii) supports a wide range of tasks, including node classification, link prediction, node clustering, and graph generation, without additional training, (iii) has in-context learning capabilities, and (iv) does not rely on pretrained LLMs. In particular, existing graph foundation models often require training additional classification heads or feature projectors to accommodate new graphs or new labels, whereas Acacia does not. Moreover, existing graph foundation models often gain their capabilities by being stitched together with pretrained LLMs, whereas Acacia is trained from scratch using only the Common Crawl web graph. This is also an important result because it provides evidence that graph models can acquire emergent capabilities from scratch like LLMs.

Fri 25 SeptArtificial IntelligenceMachine Learning
The gist
Understanding and analyzing large networks like the web is difficult because each graph has different features and labels. The authors introduce Acacia, a new kind of graph model trained from scratch on the web graph that can handle many tasks like classifying nodes or predicting links without extra training. It works with various types of features and doesn’t depend on message-passing from large language models. This shows that graph models alone can develop advanced abilities similar to language models.
Open → 2609.30894v1

Signed graph pre training improves learning with negative and positive links

Signed Graph Pre-Training and Prompt Learning

Abstract: Signed graphs arise in trust--distrust networks, financial correlation systems, biological interaction graphs, and many other domains in which edges can be positive or negative and may also be directed. While signed graph neural networks have improved task-specific learning, graph transfer learning on signed graphs remains underdeveloped. In this paper, we introduce TopoSIGN, a pioneer topology-guided graph pre-training and prompt learning framework for signed graphs. TopoSIGN combines a structural encoder built on the magnetic signed Laplacian with a novel persistent-homology branch that summarizes signed topology through Dowker-complex persistence images. The fused embeddings are then transferred to a prompt learning function. Experimental results on synthetic and real-world datasets demonstrate the efficacy of TopoSIGN in extracting useful structural information in signed graphs, as well as the adaptability and flexibility of the proposed general framework.

Tue 22 SeptMachine Learning
The gist
Graphs with positive and negative connections show up in many areas like social networks and biology, but learning from these graphs across different tasks is hard. The authors introduce TopoSIGN, a new system that learns patterns in these signed graphs by looking at their shape and structure in two ways. It combines a special math tool called the magnetic signed Laplacian with another tool that captures complex topological features, making it better at understanding these graphs. Experiments show TopoSIGN helps algorithms learn better from signed graphs and adapt to new problems.
Open → 2609.25722v1

Efficient search finds stronger communities in time-changing bipartite graphs

WCCS: Efficient Wedge Conductance Community Search over Large Temporal Bipartite Graphs (Full Paper)

Abstract: Bipartite graphs are ubiquitous for modeling complex interactions between two distinct entity types across numerous practical applications such as e-commerce, academic networks, and social systems. Despite significant progress in community search over bipartite graphs, most prior work is limited to static settings and ignores the rich temporal dynamics present in real-world networks. Moreover, existing methods typically adopt edge-centric measures and strict consecutivity constraints, failing to capture higher-order interactions and frequent yet non-consecutive activities. More importantly, they often neglect the crucial community-quality requirements of both internal cohesiveness and external sparsity, failing to identify critical nodes or including many irrelevant nodes. To address these dilemmas, we propose the novel problem of \emph{Wedge Conductance Community Search (WCCS)}, which aims to identify a query-dependent community that is not only structurally and temporally cohesive but also well-separated from the rest of the network over non-consecutive timestamps. We formalize WCCS by generalizing the classical $(α,β)$-core to a higher-order $(α,β,τ)$-wedge core, and by proposing a novel temporal wedge conductance metric that explicitly balances internal density and external sparsity. To solve WCCS efficiently, we first develop an online priority-driven filter-and-expand framework with several effective pruning techniques and a powerful geometric slope optimization for rapid temporal wedge conductance calculation. Subsequently, to further improve scalability, we propose an offline compressed index to accelerate search. Finally, comprehensive experiments on seven real-world datasets demonstrate the effectiveness, efficiency, and scalability of our solutions compared to eight competitors.

Tue 15 SeptSocial and Information Networks
The gist
Bipartite graphs model relationships between two types of entities, like buyers and products, but many existing methods miss how these connections change over time. The authors introduce a new way to find groups, or communities, that are tightly connected and well separated, even if their interactions happen at irregular times. They develop a new measure called temporal wedge conductance and efficient methods to identify these communities quickly on large datasets. Their approach works better than previous ones by capturing more complex interaction patterns without requiring connections to happen in strict order.
Open → 2609.16882v1

CUNO improves graph model unlearning for large data deletions

CUNO: Curriculum and Preference Optimization for Stable Graph Unlearning under Mass Deletion

Abstract: Graph unlearning removes the influence of designated training data from a trained graph model without retraining from scratch. However, existing methods suffer a sharp drop in model utility under large deletion ratios (mass deletion), a phenomenon we refer to as catastrophic unlearning. We find that a key cause is the uniform treatment of all deleted samples, which is particularly damaging in graph learning: structural dependencies cause different nodes to play vastly different roles in the learned model, yet existing methods apply the same forgetting operation to the entire forget set. Based on this insight, we propose CUNO, a curriculum-based graph unlearning framework that removes the forget set progressively, ordering samples by their estimated unlearning difficulty across multiple stages. CUNO further employs a distribution-level negative preference optimization (NPO) objective at each curriculum stage that steers the model away from its original behavior on the current forget subset while preserving retained performance. Our theoretical analysis shows that the curriculum design is most beneficial when the forget set spans a wide range of unlearning difficulty, a condition naturally satisfied under mass deletion. Comprehensive experiments confirm that CUNO consistently mitigates catastrophic unlearning: at 20% deletion, it retains 74% of the original utility compared to 26-53% for existing methods, and maintains more than half the original utility even at 50% deletion. Our code is publicly available at https://anonymous.4open.science/r/cuno-D4FF.

Tue 8 SeptMachine LearningArtificial Intelligence
The gist
When parts of data need to be removed from a graph-based AI model, simply forgetting them all at once often harms the model’s performance badly. The authors show that treating all deleted data equally misses the fact that some nodes in a graph are more important than others. They introduce CUNO, a step-by-step way to remove data, focusing first on easier-to-forget parts while guiding the model away from old behaviors on deleted data. Tests show this approach keeps the model working much better even when up to half the data is removed.
Open → 2609.08244v1