Graph Neural Networks (GNNs) have achieved significant success in addressing node classification tasks. However, the effectiveness of traditional GNNs degrades on heterophilic graphs, where connected nodes often belong to different labels or properties. While recent work has introduced mechanisms to improve GNN performance under heterophily, certain key limitations still exist. Most existing models apply a fixed aggregation depth across all nodes, overlooking the fact that nodes may require different propagation depths based on their local homophily levels and neighborhood structures. Moreover, many methods are tailored to either homophilic or heterophilic settings, lacking the flexibility to generalize across both regimes. To address these challenges, we develop a theoretical framework that links local structural and label characteristics to information propagation dynamics at the node level. Our analysis shows that optimal aggregation depth varies across nodes and is critical for preserving class-discriminative information. Guided by this insight, we propose a novel adaptive-depth GNN architecture that dynamically selects node-specific aggregation depths using theoretically grounded metrics. Our method seamlessly adapts to both homophilic and heterophilic patterns within a unified model. Extensive experiments demonstrate that our approach consistently enhances the performance of standard GNN backbones across diverse benchmarks.

Message passing is the core operation in graph neural networks, where each node updates its embeddings by aggregating information from its neighbors. However, in deep architectures, this process often leads to diminished expressiveness. A popular solution is the use of residual connections, where the input from the current (or initial) layer is added to the aggregated neighbor information to preserve embeddings across layers. Following a recent line of research, we investigate an adaptive residual scheme in which different nodes have varying residual strengths. We prove that this approach prevents oversmoothing; particularly, we show that the Dirichlet energy of the embeddings remains bounded away from zero. This is the first theoretical guarantee not only for the adaptive setting, but also for static residual connections (where residual strengths are shared across nodes) with activation functions. Furthermore, based on an extensive set of experiments, this adaptive approach is shown to outperform the standard and state-of-the-art message passing mechanisms, especially on heterophilic graphs. To improve the time complexity of our approach, we introduce a variant in which residual strengths are not learned but instead set heuristically, a choice that performs as well as the learnable version.

The advent of online social networks has facilitated fast and wide spread of information. However, some users, especially members of minority groups, may be less likely to receive information spreading on the network, due to their disadvantaged network position. We study the optimization problem of adding new connections to a network to enhance fairness in information access among different demographic groups. We provide a concrete formulation of this problem where information access is measured in terms of resistance distance, {offering a new perspective that emphasizes global network structure and multi-path connectivity.} The problem is shown to be NP-hard. We propose a simple greedy algorithm which turns out to output accurate solutions, but its run time is cubic, which makes it undesirable for large networks. As our main technical contribution, we reduce its time complexity to linear, leveraging several novel approximation techniques. In addition to our theoretical findings, we also conduct an extensive set of experiments using both real-world and synthetic datasets. We demonstrate that our linear-time algorithm can produce accurate solutions for networks with millions of nodes.

Random walk centrality is a fundamental metric in graph mining for quantifying node importance and influence, defined as the weighted average of hitting times to a node from all other nodes. Despite its ability to capture rich graph structural information and its wide range of applications, computing this measure for large networks remains impractical due to the computational demands of existing methods. In this paper, we present a novel formulation of random walk centrality, underpinning two scalable algorithms: one leveraging approximate Cholesky factorization and sparse inverse estimation, while the other sampling rooted spanning trees. Both algorithms operate in near-linear time and provide strong approximation guarantees. Extensive experiments on large real-world networks, including one with over 10 million nodes, demonstrate the efficiency and approximation quality of the proposed algorithms.

Influence maximization is a key topic in data mining, with broad applications in social network analysis and viral marketing. In recent years, researchers have increasingly turned to machine learning techniques to address this problem. By learning the underlying diffusion processes from data, these methods improve the generalizability of solutions while optimizing objectives to identify the optimal seed set for maximizing influence. Nonetheless, two fundamental challenges remain unresolved: (1) While Graph Neural Networks (GNNs) are increasingly employed to learn diffusion models, their traditional architectures often fail to capture the complex dynamics of influence diffusion, (2) Designing optimization objectives is inherently difficult due to the combinatorial explosion associated with solving this problem. To address these challenges, we propose a novel framework, DeepSN. Our framework employs sheaf neural diffusion to learn diverse influence patterns in a data-driven, end-to-end manner, providing enhanced separability in capturing diffusion characteristics. We also propose an optimization technique that accounts for overlapping influence between vertices, significantly reducing the search space and facilitating the identification of the optimal seed set efficiently. Finally, we conduct extensive experiments on both synthetic and real-world datasets to demonstrate the effectiveness of our framework.

Consider a social network where each node (user) is blue or red, corresponding to positive or negative opinion on a topic. In the voter model, in discrete time rounds, each node picks a neighbour uniformly at random and adopts its colour. Despite its significant popularity, this model does not capture some fundamental real-world characteristics such as the difference in the strengths of connections, individuals with no initial opinion, and users who are reluctant to update. To address these issues, we introduce a generalisation of the voter model. We study the problem of selecting a set of seed blue nodes to maximise the expected number of blue nodes after some rounds. We prove that the problem is NP-hard and provide a polynomial time approximation algorithm with the best possible approximation guarantee. Our experiments on real-world and synthetic graph data demonstrate that the proposed algorithm outperforms other algorithms. We also prove that the process could take an exponential number of rounds to converge. However, if we limit ourselves to strongly connected graphs, the convergence time is polynomial and the convergence period (size of the stationary configuration) is bounded by the highest common divisor of cycle lengths in the network.

Graph Neural Networks (GNNs) have demonstrated strong representation learning capabilities for graph-based tasks. Recent advances on GNNs leverage geometric properties, such as curvature, to enhance their representation capabilities by modeling complex connectivity patterns and information flow within graphs. However, most existing approaches primarily focus on discrete graph topology, overlooking diffusion dynamics and task-specific dependencies essential for effective learning. To address this, we propose a learnable integration of Bakry-Émery curvature, which captures both structural and diffusion aspects of information propagation. We develop an efficient, learnable approximation strategy, making curvature computation scalable for large graphs. Furthermore, we introduce an adaptive depth mechanism that dynamically adjusts message-passing layers per vertex based on its curvature, ensuring efficient propagation. Our theoretical analysis establishes a link between curvature and feature distinctiveness, showing that high-curvature vertices require fewer layers, while low-curvature ones benefit from deeper propagation. Extensive experiments on diverse downstream tasks validate the effectiveness of our approach, showing that the proposed depth-adaptive mechanism consistently uplifts the performance of a wide range of GNN architectures.

With the rapid evolution and diversification of Internet applications, their communication-quality criteria are continuously evolving. To globally optimize communication quality, the Internet's control plane thus needs to optimize inter-domain paths on diverse criteria, and should provide extensibility for adding new criteria or modifying existing ones. However, current inter-domain routing protocols and proposals satisfy these requirements at best to a limited degree.

We study how the stubbornness of social network users influences opinion polarization and disagreement. Our work is in the context of the popular Friedkin-Johnson opinion formation model, where users update their opinion as a function of the opinion of their connections and their own innate opinion. Stubbornness then is formulated in terms of the stress a user puts on its innate opinion.

We introduce and study a novel majority-based opinion diffusion model. Consider a graph G , which represents a social network. Assume that initially a subset of nodes, called seed nodes or early adopters, are colored either black or white, which correspond to positive or negative opinion regarding a consumer product or a technological innovation. Then, in each round an uncolored node, which is adjacent to at least one colored node, chooses the most frequent color among its neighbors. Consider a marketing campaign which advertises a product of poor quality and its ultimate goal is that more than half of the population believe in the quality of the product at the end of the opinion diffusion process. We focus on three types of attackers which can select the seed nodes in a deterministic or random fashion and manipulate almost half of them to adopt a positive opinion toward the product (that is, to choose black color). We say that an attacker succeeds if a majority of nodes are black at the end of the process. Our main purpose is to characterize classes of graphs where an attacker cannot succeed. In particular, we prove that if the maximum degree of the underlying graph is not too large or if it has strong expansion properties, then it is fairly resilient to such attacks. Furthermore, we prove tight bounds on the stabilization time of the process (that is, the number of rounds it needs to end) in both settings of choosing the seed nodes deterministically and randomly. We also provide several hardness results for some optimization problems regarding stabilization time and choice of seed nodes.

The Kirchhoff index, which is the sum of the resistance distance between every pair of nodes in a network, is a key metric for gauging network performance, where lower values signify enhanced performance. In this paper, we study the problem of minimizing the Kirchhoff index by adding edges. We first provide a greedy algorithm for solving this problem and give an analysis of its quality based on the bounds of the submodularity ratio and the curvature. Then, we introduce a gradient-based greedy algorithm as a new paradigm to solve this problem. To accelerate the computation cost, we leverage geometric properties, convex hull approximation, and approximation of the projected coordinate of each point. To further improve this algorithm, we use pre-pruning and fast update techniques, making it particularly suitable for large networks. Our proposed algorithms have nearly-linear time complexity. We provide extensive experiments on ten real networks to evaluate the quality of our algorithms. The results demonstrate that our proposed algorithms outperform the state-of-the-art methods in terms of efficiency and effectiveness. Moreover, our algorithms are scalable to large graphs with over 5 million nodes and 12 million edges.

To obtain a foundational understanding of timeline algorithms and viral content in shaping public opinions, computer scientists started to study augmented versions of opinion formation models from sociology. In this paper, we generalize the popular Friedkin--Johnsen model to include the effects of external media sources on opinion formation. Our goal is to mathematically analyze the influence of biased media, arising from factors such as manipulated news reporting or the phenomenon of false balance. Within our framework, we examine the scenario of two opposing media sources, which do not adapt their opinions like ordinary nodes, and analyze the conditions and the number of periods required for radicalizing the opinions in the network. When both media sources possess equal influence, we theoretically characterize the final opinion configuration. In the special case where there is only a single media source present, we prove that media sources which do not adapt their opinions are significantly more powerful than those which do. Lastly, we conduct the experiments on real-world and synthetic datasets, showing that our theoretical guarantees closely align with experimental simulations.

We study resistance eccentricity, a fundamental metric in network science for measuring the structural significance of a node. For a node in a graph, the resistance eccentricity is its maximum resistance distance to all other nodes. Fast computation of resistance eccentricity for a given subset of nodes is essential for a wide range of applications. However, a naive computation, requiring the pseudoinverse of the graph Laplacian, takes cubic time and is thus infeasible for huge networks with millions of nodes. In this paper, we devise a near-linear time algorithm to approximate the resistance eccentricity for one or multiple given nodes, accompanied by a theoretically guaranteed error bound. Furthermore, we investigate the problem of minimizing the resistance eccentricity for a given node by adding$k$missing edges to the graph, for a budget$k$. We show that while the objective function is monotone, it does not possess the submodularity property, ruling out the classical hill-climbing algorithm with theoretical guarantees. Instead, we propose two fast heuristic algorithms to approximately solve this problem. Then, we conduct extensive experiments on different networks with sizes up to several million nodes, demonstrating the superiority of our algorithms in terms of efficiency and effectiveness.

Thebiharmonic distance (BD) is a fundamental metric that measures the distance of two nodes in a graph. It has found applications in network coherence, machine learning, and computational graphics, among others. In spite of BD's importance, efficient algorithms for the exact computation or approximation of this metric on large graphs remain notably absent. In this work, we provide several algorithms to estimate BD, building on a novel formulation of this metric. These algorithms enjoy locality property (that is, they only read a small portion of the input graph) and at the same time possess provable performance guarantees. In particular, our main algorithms approximate the BD between any node pair with an arbitrarily small additive error ε in time O(1/ε2 poly(log n/ε)). Furthermore, we perform an extensive empirical study on several benchmark networks, validating the performance and accuracy of our algorithms.

Abstract Consider a graph G, which represents a social network, and assume that initially each node is either blue or white (corresponding to its opinion on a certain topic). In each round, all nodes simultaneously update their color to the most frequent color in their neighborhood. This is called the Majority Model (MM) if a node keeps its color in case of a tie and the Random Majority Model (RMM) if it chooses blue with probability 1/2 and white otherwise. We study the convergence properties of the above models, including stabilization time, periodicity, and the number of stable configurations. In particular, we prove that the stabilization time in RMM can be exponential in the size of the graph, which is in contrast with the previously known polynomial bound on the stabilization time of MM. We provide some bounds on the minimum size of a winning set, which is a set of nodes whose agreement on a color in the initial coloring enforces the process to end in a coloring where all nodes share that color. Furthermore, we calculate the expected final number of blue nodes for a random initial coloring, where each node is colored blue independently with some fixed probability, on cycle graphs. Finally, we conduct some experiments which complement our theoretical findings and also let us investigate other aspects of the models.

Consider a graph G and suppose that initially each node is colored either black or white. In the majority model, in each round all nodes simultaneously update their color to the most frequent color among their neighbors. Experiments on the graph data from the real world social networks (SNs) suggest that if an extremely small set of high-degree nodes, often referred to as the elites, all agree on a color, that color becomes the dominant color at the end of the process. We propose two countermeasures that can be adopted by individual nodes relatively easily and guarantee that the elites will not have this disproportionate power to engineer the dominant output color. The first countermeasure essentially requires each node to make some new connections at random, while the second one demands the nodes to be more reluctant towards changing their color. We verify their effectiveness and correctness both theoretically and experimentally. We also investigate the majority model and a variant of it when the initial coloring is random on the real world SNs and several random graph models. In particular, our results on the Erdős-Rényi and regular random graphs confirm or support several theoretical findings or conjectures by the prior work regarding the threshold behavior of the process.

Critical nodes in networks are extremely vulnerable to malicious attacks to trigger negative cascading events such as the spread of misinformation and diseases. Therefore, effective moderation of critical nodes is very vital for mitigating the potential damages caused by such malicious diffusions. The current moderation methods are computationally expensive. Furthermore, they disregard the fundamental metric of information centrality, which measures the dissemination power of nodes. We investigate the problem of removing$k$edges from a network to minimize the information centrality of a target node$v$while preserving the network's connectivity. We prove that this problem is computationally challenging: it is NP-complete and its objective function is not supermodular. However, we propose three approximation greedy algorithms using novel techniques such as random walk-based Schur complement approximation and fast sum estimation. One of our algorithms runs in nearly linear time in the number of edges. To complement our theoretical analysis, we conduct a comprehensive set of experiments on synthetic and real networks with over one million nodes. Across various settings, the experimental results illustrate the effectiveness and efficiency of our proposed algorithms.

Let G be a graph, which represents a social network, and suppose each node v has a threshold value τ(v). Consider an initial configuration, where each node is either positive or negative. In each discrete time step, a node v becomes/remains positive if at least τ(v) of its neighbors are positive and negative otherwise. A node set S is a Target Set (TS) whenever the following holds: if S is fully positive initially, all nodes in the graph become positive eventually. We focus on a generalization of TS, called Timed TS (TTS), where it is permitted to assign a positive state to a node at any step of the process, rather than just at the beginning. We provide graph structures for which the minimum TTS is significantly smaller than the minimum TS, indicating that timing is an essential aspect of successful target selection strategies. Furthermore, we prove tight bounds on the minimum size of a TTS in terms of the number of nodes and maximum degree when the thresholds are assigned based on the majority rule. We show that the problem of determining the minimum size of a TTS is NP-hard and provide an Integer Linear Programming formulation and a greedy algorithm. We evaluate the performance of our algorithm by conducting experiments on various synthetic and real-world networks. We also present a linear-time exact algorithm for trees.

We study a rumor spreading model where individuals are connected via a network structure. Initially, only a small subset of the individuals are spreading a rumor. Each individual who is connected to a spreader, starts spreading the rumor with some probability as a function of their trust in the spreader, quantified by the Jaccard similarity index. Furthermore, the probability that a spreader diffuses the rumor decreases over time until they fully lose their interest and stop spreading. We focus on determining the graph parameters which govern the magnitude and pace that the rumor spreads in this model. We prove that for the rumor to spread to a sizable fraction of the individuals, the network needs to enjoy ``strong'' expansion properties and most nodes should be in ``well-connected'' communities. Both of these characteristics are, arguably, present in real-world social networks up to a certain degree, shedding light on the driving force behind the extremely fast spread of rumors in social networks. Furthermore, we formulate a large range of countermeasures to cease the spread of a rumor. We introduce four fundamental criteria which a countermeasure ideally should possess. We evaluate all the proposed countermeasures by conducting experiments on real-world social networks such as Facebook and Twitter. We conclude that our novel decentralized countermeasures (which are executed by the individuals) generally outperform the previously studied centralized ones (which need to be imposed by a third entity such as the government).

We prove lower bounds for higher-order methods in smooth non-convex finite-sum optimization. Our contribution is threefold: We first show that a deterministic algorithm cannot profit from the finite-sum structure of the objective and that simulating a pth-order regularized method on the whole function by constructing exact gradient information is optimal up to constant factors. We further show lower bounds for randomized algorithms and compare them with the best-known upper bounds. To address some gaps between the bounds, we propose a new second-order smoothness assumption that can be seen as an analogue of the first-order mean-squared smoothness assumption. We prove that it is sufficient to ensure state-of-the-art convergence guarantees while allowing for a sharper lower bound.

We introduce and study a novel majority based opinion diffusion model. Consider a graph G, which represents a social network. Assume that initially a subset of nodes, called seed nodes or early adopters, are colored either black or white, which correspond to positive or negative opinion regarding a consumer product or a technological innovation. Then, in each round an uncolored node, which is adjacent to at least one colored node, chooses the most frequent color among its neighbors. Consider a marketing campaign which advertises a product of poor quality and its ultimate goal is that more than half of the population believe in the quality of the product at the end of the opinion diffusion process. We focus on three types of attackers which can select the seed nodes in a deterministic or random fashion and manipulate almost half of them to adopt a positive opinion toward the product (that is, to choose black color). We say that an attacker succeeds if a majority of nodes are black at the end of the process. Our main purpose is to characterize classes of graphs where an attacker cannot succeed. In particular, we prove that if the maximum degree of the underlying graph is not too large or if it has strong expansion properties, then it is fairly resilient to such attacks. Furthermore, we prove tight bounds on the stabilization time of the process (that is, the number of rounds it needs to end) in both settings of choosing the seed nodes deterministically and randomly. We also provide several hardness results for some optimization problems regarding stabilization time and choice of seed nodes.

Consider a graph G, representing a social network. Assume that initially each node is colored either black or white, which corresponds to a positive or negative opinion regarding a consumer product or a technological innovation. In the majority model, in each round all nodes simultaneously update their color to the most frequent color among their connections. Experiments on the graph data from the real world social networks (SNs) suggest that if all nodes in an extremely small set of high-degree nodes, often referred to as the elites, agree on a color, that color becomes the dominant color at the end of the process. We propose two countermeasures that can be adopted by individual nodes relatively easily and guarantee that the elites will not have this disproportionate power to engineer the dominant output color. The first countermeasure essentially requires each node to make some new connections at random while the second one demands the nodes to be more reluctant towards changing their color (opinion). We verify their effectiveness and correctness both theoretically and experimentally. We also investigate the majority model and a variant of it when the initial coloring is random on the real world SNs and several random graph models. In particular, our results on the Erdős-Rényi, and regular random graphs confirm or support several theoretical findings or conjectures by the prior work regarding the threshold behavior of the process. Finally, we provide theoretical and experimental evidence for the existence of a poly-logarithmic bound on the expected stabilization time of the majority model.

Consider a graph G and an initial configuration where each node is black or white. Assume that in each round all nodes simultaneously update their color based on a predefined rule. In the r-threshold (resp. α-threshold) model, a node becomes black if at least r of its neighbors (resp. α fraction of its neighbors) are black, and white otherwise. A node set D is said to be a dynamic monopoly if black color takes over once all nodes in D are black. We provide several tight bounds on the minimum size of a dynamic monopoly in terms of different graph parameters. Furthermore, we prove some bounds on the stabilization time of the process. Finally, we also establish bounds on the minimum size of a dynamic monopoly and the stabilization time in the aforementioned models, as a function of the underlying graph's expansion.

Consider a graph G and an initial random configuration, where each node is black with probability p and white otherwise, independently. In discrete-time rounds, each node becomes black if it has at least r black neighbors and white otherwise. We prove that this basic process exhibits a threshold behavior with two phase transitions when the underlying graph is a d-dimensional torus and identify the threshold values.

Assume for a graph G=(V,E) and an initial configuration, where each node is blue or red, in each discrete-time round all nodes simultaneously update their color to the most frequent color in their neighborhood and a node keeps its color in case of a tie. We study the behavior of this basic process, which is called majority model, on the Erdös-Rényi random graph G_{n,p} and regular expanders. First we consider the behavior of the majority model on G_{n,p} with an initial random configuration, where each node is blue independently with probability p_b and red otherwise. It is shown that in this setting the process goes through a phase transition at the connectivity threshold, namely (log n)/n. Furthermore, we say a graph G is lambda-expander if the second-largest absolute eigenvalue of its adjacency matrix is lambda. We prove that for a Delta-regular lambda-expander graph if lambda/Delta is sufficiently small, then the majority model by starting from (1/2-delta)n blue nodes (for an arbitrarily small constant delta>0) results in fully red configuration in sub-logarithmically many rounds. Roughly speaking, this means the majority model is an "efficient" and "fast" density classifier on regular expanders. As a by-product of our results, we show regular Ramanujan graphs are asymptotically optimally immune, that is for an n-node Delta-regular Ramanujan graph if the initial number of blue nodes is s <= beta n, the number of blue nodes in the next round is at most cs/Delta for some constants c,beta>0. This settles an open problem by Peleg [Peleg, 2014].