On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications

Danai Koutra; Di Jin; John Boaz Lee; Nesreen K. Ahmed; Ryan A. Rossi; Sungchul Kim

REVIEW 3 major objections 5 minor 3 references

On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Walk-based graph embeddings capture communities, not structural roles.

desk verdict A genuinely useful taxonomy of community- vs role-based embeddings, with a correct but narrow theorem that Section 4.2 over-extends to trained GNNs. read the letter →

arxiv 1908.08572 v2 pith:WZIXF5G3 submitted 2019-08-22 cs.SI cs.LG

Ryan A. Rossi , Di Jin , Sungchul Kim , Nesreen K. Ahmed , Danai Koutra , John Boaz Lee This is my paper · ORCID

classification cs.SIcs.LG

keywords role-basedstructuralembeddingscommunity-basedproximitysimilarityrandomwalksfeaturediffusiongraphletsnetworkrepresentationlearning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Networks can be organized in two fundamentally different ways: by community, where nodes are grouped because they are close and densely interconnected, or by structural role, where nodes are grouped because their local wiring is similar even when the nodes are far apart. This paper argues that the mechanisms behind most popular node-embedding methods, random walks and feature propagation, inherently produce community-based embeddings rather than role-based ones. It proves that repeated Laplacian smoothing drives feature vectors of nodes in the same community to become identical or degree-proportional, and that walks on a low-conductance graph almost never leave their starting community. The consequence is that methods such as DeepWalk, node2vec, LINE, GCN, and GraphSAGE should be understood as proximity embeddings, while role-based structure requires graphlet and motif features, feature-based walks, or matrix factorization over structural features.

What carries the argument

The load-bearing object is Theorem 4.1, the Laplacian-smoothing convergence theorem: for a connected non-bipartite graph, $\lim_{t\to\infty}(D^{-1}A)^t X = \mathbf{1}y^{\top}$ and $\lim_{t\to\infty}(D^{-1/2}AD^{-1/2})^t X = D^{-1/2}\mathbf{1}y^{\top}$. Together with the conductance bound that an $\ell$-step walk stays in a low-conductance set $C$ with probability at least $1-\ell\Phi(C)/2$, this theorem converts the intuition that walks and diffusions stay inside communities into the paper's classification claim. It also marks the escape hatch: graphlet and motif features and feature-based walks are role-based precisely because they avoid smoothing raw node-id proximity.

What would settle it

On a graph formed from two identical dense clusters joined by one edge, train an explicit-walk embedding such as DeepWalk or node2vec and measure the distance between nodes that occupy the same structural position in the two clusters. The paper's claim predicts those role-aligned cross-cluster pairs are no closer than arbitrary cross-cluster pairs because the walks rarely cross the bridge; if they come out closer than same-cluster non-role pairs, the community-based conclusion is contradicted.

Watch

Extended reading notes

Core claim

The paper's central claim is that any embedding method built on implicit walks (counts of walks between nodes) or explicit walks (sampled sequences of node ids) outputs community-based, proximity-driven embeddings, and so does any method built on feature propagation over the graph. For explicit walks, the argument is quantitative: in a graph with good communities, an $\ell$-step random walk stays inside its starting community with probability at least $1-\ell\Phi(C)/2$, so the contexts a walk-based model sees are dominated by same-community nodes. For propagation, Theorem 4.1 shows that repeatedly applying the smoothing operators $D^{-1}A$ or $D^{-1/2}AD^{-1/2}$ to any feature matrix $X$ drives all node vectors to a common limit, identical vectors in the first case and degree-proportional vectors in the second, meaning nodes in the same community become indistinguishable. The paper further argues that claims that such methods preserve structural equivalence or regular equivalence are not well-posed, because those equivalences are defined on the graph itself, not on embedding vectors; role-based embeddings require structural features such as graphlets, feature-based walks, or factorization of a structural feature matrix.

Load-bearing premise

The argument assumes the graph is made of genuinely dense clusters with few links between them, so that a random walk or diffusion almost never crosses from one cluster to another; if that assumption fails, the proof that walk-based embeddings are community-based does not go through.

Editorial extensions

If this is right

DeepWalk, node2vec, LINE, and GraRep should be described and used as proximity or community embeddings; their strong results on homophily-driven node classification reflect that mechanism.
GCN, GraphSAGE, and other feature-propagation models are community-based and cannot by themselves serve as structural-role embeddings for transfer across networks.
Claims that an embedding method preserves structural or regular equivalence are not well-posed, because those equivalences are defined on the original graph, not on embedding vectors.
Role-based embeddings are the appropriate tool for across-network classification, weak-homophily or heterophily settings, long-range link prediction, network alignment, and structural anomaly detection.
A new embedding method can be classified by its mechanism: raw walks or raw diffusion makes it community-based, while graphlets, feature-based walks, or structural-feature matrix factorization make it role-based.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An inference I draw beyond the paper: any method whose input is a function of the adjacency matrix, including attention-based message passing without structural features, likely inherits the same community bias, because the same confinement argument applies to its diffusion.
The theorem is asymptotic, so finite-depth models on graphs without clear community structure may sit between roles and communities; a testable prediction is that their behavior degrades exactly when conductance stops being small.
The mechanism test suggests a practical benchmark: role-aligned nodes in disconnected identical components should be separated by walk-based embeddings but aligned by graphlet-based role embeddings; applying this benchmark to new methods would reveal which family they belong to.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This is the clearest written treatment I know of the roles-versus-communities distinction in graph embeddings. The taxonomy is genuinely useful: Table 2 alone is worth the download, and the formal embedding-based equivalences in Section 3 are a real service to a literature that routinely confuses structural equivalence with proximity. The applications section is practical and sensible. I would send this to review.

The main theorem, Theorem 4.1, is correct as stated: under connectedness and non-bipartiteness, repeated application of the random-walk or normalized Laplacian smoothing operators makes features converge to a common or degree-proportional vector. That is standard spectral theory, but it is properly stated and proved.

The soft spot is Section 4.2. The paper classifies GCN and GraphSAGE as community-based because their aggregation resembles Laplacian smoothing. The proof, however, only covers the linear infinite-time limit. A real GCN layer has a nonlinearity, learned weights, and a small finite number of layers. With finite layers and shared weights, two nodes with isomorphic local neighborhoods and identical input features receive identical embeddings. That is role-like, not community-like. The stress-test note lands: the claim that trainable parameters merely learn better community embeddings is asserted, not shown.

There is a second caveat, in Section 4.1. The argument that walk-based methods are community-based relies on the graph having good low-conductance communities (Equation 10). On graphs without strong community structure, walks mix more globally, and the same reasoning does not establish a community-based embedding. This makes the universal claims conditional, not false.

One circularity is worth noting but minor: Definition 14 builds "not correlated with proximity" into feature-based structural similarity, so the later claim that graphlet features are role-based is partly true by construction. That is a reasonable convention, but it is a convention, not an empirical discovery.

The citation pattern is fine. The heavy reliance on Rossi and Ahmed (2015) is natural because this paper extends that framework; it is not a flaw in itself.

Bottom line: this paper deserves a serious referee, and I would ask for revision that makes Section 4.2 explicitly finite-depth and conditional, acknowledging that trained GNNs can learn role-like functions. The taxonomy will be cited and used regardless.

Referee Report

3 major / 5 minor

Summary. The paper distinguishes two complementary notions in network embeddings: community-based (proximity/density) embeddings and role-based (structural similarity) embeddings. It formalizes these notions, proposes feature/embedding-based role equivalences, and identifies general mechanisms that allegedly produce each type: random walks and feature propagation/diffusion are claimed to always yield community-based embeddings, while graphlets, feature-based walks, and feature-based matrix factorization are claimed to yield role-based embeddings. The main formal result is Theorem 4.1, showing that repeated Laplacian smoothing converges to identical or degree-proportional feature vectors. The paper also categorizes existing methods (DeepWalk, node2vec, LINE, GCN, GraphSAGE, etc.) into the two classes and discusses applications where each type is appropriate.

Significance. If the taxonomy were fully established, it would be valuable: practitioners could decide which embedding method to use based on the graph's community structure and the downstream task. The paper's conceptual distinction between communities and roles, and its emphasis on mechanisms rather than individual methods, are useful contributions. Theorem 4.1 is a correct and standard spectral result, and the paper's discussion of applications (homophily vs. heterophily, cross-network transfer, anomaly detection) is thoughtful. The main deficit is that the broad classification claims go beyond what the theorem and the surrounding arguments actually prove; several load-bearing assertions about specific method families are supported only by heuristic reasoning.

major comments (3)

[Section 4.1, after Eq. (10)] The universal claim that 'any walk-based embedding method that uses either implicit walks or explicit walks outputs community-based embeddings' is not established for graphs without strong community structure. The argument relies on Eq. (10), which bounds the probability of an ℓ-step walk staying inside a low-conductance community C. For graphs with high conductance or no clear communities, this bound is vacuous, and random walks may mix globally, so the embeddings need not be community-based. Since this claim is load-bearing for the paper's central taxonomy, it should be qualified to graphs with sufficiently low-conductance communities, or a separate proof must be provided for the general case.
[Section 4.2, Theorem 4.1 and Eq. (18)] Theorem 4.1 applies only to the linear smoothing operators (D^{-1}A)^t and (D^{-1/2}AD^{-1/2})^t. It does not cover GCN's actual layer, which includes a nonlinearity σ and learned per-layer weight matrices W^{(t)} (Eq. 18), nor the aggregation used by GraphSAGE. The paper's assertion that trainable parameters merely 'learn better community/proximity-based embeddings' is an extrapolation, not a consequence of the theorem. In fact, a finite-layer GCN with shared weights can map structurally identical nodes (i.e., nodes with isomorphic k-hop neighborhoods and identical input features) to identical embeddings, which would satisfy the role-based condition in Definition 14 rather than a community-based condition. Thus the classification of GCN and GraphSAGE as community-based is not proven by the supplied argument.
[Section 3.2, Definition 14] Definition 14 defines role-based features partly by condition (2), which requires that the features are 'not correlated with graph proximity and/or density.' The paper later asserts that graphlet counts are role-based features without independently demonstrating that they satisfy this uncorrelatedness condition. In practice, graphlet counts are often correlated with degree, density, and community structure, so this condition is non-trivial and not automatic. Consequently, the claim that graphlet-based methods (Section 5.1) yield role-based embeddings rests in part on an assumption embedded in the definition rather than on an independent proof, which is a circularity concern for the taxonomy.

minor comments (5)

[Section 3.2, Definition 8] The header 'Structural eqivalence' contains a typo; it should read 'Structural equivalence.'
[Theorem 4.1 statement] The statement that Eq. (19) 'converges to identical feature vectors for all nodes' is imprecise: the limit matrix has identical rows, but the value of the common vector y depends on the initial features X and the graph structure. Explicitly stating that y is a linear function of X would avoid confusion.
[Table 3] The column headings in Table 3 are not fully aligned with the checkmarks; for example, the 'Features/attributes' column appears to be checked for several methods where it is unclear whether the method consumes node attributes as input. Clarifying the legend would improve readability.
[Section 4.1, after Eq. (12)] The claim that 'any matrix factorization method applied to A directly results in community-based embeddings' is overly broad and appeared without a formal proof in this work; it relies on a citation to prior work and would benefit from at least a brief justification or a pointer to the specific result.
[Section 5.1, Figure 3] Figure 3 is referenced in the text but does not appear in the body of the paper at the point of reference; the figure placement should be adjusted so that readers can view the graphlets and orbits when they are discussed.

Circularity Check

3 steps flagged · score 4.0 of 10

The taxonomy is partly anchored in the paper's own Definition 14, and the GCN classification is assumed rather than derived; however, Theorem 4.1 and the conductance argument provide independent mathematical content.

self definitional [Section 3.2, Definition 14; Section 5.1, first paragraph]
"Let xi and xj be structural embeddings and K be a similarity function, then we say node i and j are ϵ-structurally similar for any ϵ > 0 iff (1) xi and xj encode structural properties of i and j in G ... (2) xi and xj are not correlated with graph proximity and/or density (communities) in G ... As such, graphlets (and their edge orbits) capture precisely the notion of role."

The definition of feature-based structural similarity already requires that role-based features be 'not correlated with graph proximity and/or density (communities)'. The later conclusion that graphlet features are role-based is therefore reached by checking the definition rather than by an independent derivation: any feature declared structural and uncorrelated with communities is role-based by construction. The paper presents this as a theoretical demonstration, but the graphlet side of the taxonomy follows directly from Definition 14 rather than from a separate proof.
other [Section 4.2, Eq. (18) and surrounding text]
"Many of the recent propagation or diffusion-based methods [Hamilton et al. 2017; Kipf and Welling 2016, 2017; Veličković et al. 2018] also incorporate trainable parameters into the diffusion process to learn better community/proximity-based embeddings. For instance, the step-wise diffusion for GCN can be defined as follows:"

The sentence introducing GCN's update states as fact the very classification the section aims to establish: the parameters are said to 'learn better community/proximity-based embeddings'. The subsequent Theorem 4.1 applies only to the linear operators (D^-1 A)^t and (D^-1/2 A D^-1/2)^t in the limit t→∞; it does not cover the nonlinearity σ, the learned per-layer weights W^(t), or finite layers in Eq. (18). Thus the conclusion that GCN and GraphSAGE are community-based is assumed in the setup rather than derived from the supplied theorem.

1 more flagged steps

self citation load bearing [Section 4.1, before Eq. (6) and after Eq. (10)]
"The connection between walk-based embeddings and communities was formally shown by Ahmed et al. [2018]. ... The above shows that random walks capture communities and thus any walk-based embedding method that uses either implicit walks (sequences of node ids) or explicit walks (number of walks between two nodes) outputs community-based embeddings."

The universal claim that every walk-based embedding method is community-based is introduced as a result previously 'formally shown' in Ahmed et al. [2018], the authors' own role2vec paper, and then restated after a conductance argument. The conductance bound in Eq. (10) concerns random walks on graphs with low-conductance communities; the step from that bound to the outputs of arbitrary embedding models trained on walks is not a formal reduction. The self-citation is load-bearing because it is invoked to rule out walk-based methods preserving structural roles, without an independent proof covering the embedding models themselves.

full rationale

The paper's mechanism analysis is not wholly circular: Theorem 4.1 is a genuine convergence result for Laplacian smoothing, and the conductance bound in Eq. (10) is an external result supporting the claim that random walks on low-conductance graphs stay inside communities. These are independent mathematical facts. However, the taxonomy is partially anchored in Definition 14, which builds the conclusion 'role-based = uncorrelated with communities' into the definition of structural similarity, making the graphlet/role-based classification follow by construction rather than proof. A second circular move occurs in Section 4.2, where GCN's update is introduced with the assertion that the trainable parameters 'learn better community/proximity-based embeddings' before Theorem 4.1 is stated; the theorem does not cover the nonlinear, learned, finite-layer setting of Eq. (18), so the GCN/GraphSAGE classification is assumed rather than derived. Finally, the universal claim that all walk-based methods are community-based is credited to the authors' own prior work (Ahmed et al. 2018) and is broader than the reproduced conductance argument. These issues make the paper's proof of its taxonomy partially definitional and partially dependent on self-citation, but the Laplacian convergence result and walk-conductance bound provide real independent content, so a score of 4 is appropriate.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central theorem is derived from standard Markov chain spectral theory, with no fitted parameters. The method taxonomy depends on two domain assumptions: low-conductance community structure and the independence of structural features from proximity. The second is built into Definition 14, which adds an ad hoc element.

assumptions (4)

standard math Spectral properties of random walk and normalized Laplacian: eigenvalues in [0,2) for connected non-bipartite graphs.
Used in the proof of Theorem 4.1, cited to Chung 1997.
domain assumption Graph G is connected and non-bipartite.
Stated before Theorem 4.1; required for convergence to a single eigenvector.
domain assumption Communities have low conductance and duC > duCbar for all u in C.
Used in Eq. (7)-(10) to show random walks stay inside communities; this is the premise that makes walk-based embeddings community-based.
ad hoc to paper Structural features (e.g., graphlet counts) are uncorrelated with graph proximity.
Definition 14 condition (2) imposes this for role-based embeddings; the paper asserts it rather than proving it for all structural features.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications." pith.science (2026). https://pith.science/paper/WZIXF5G3

@misc{pith2026190808572,
  author       = {Pith},
  title        = {Pith review of: On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WZIXF5G3}},
  note         = {Machine review of arXiv:1908.08572}
}

read the original abstract

Structural roles define sets of structurally similar nodes that are more similar to nodes inside the set than outside, whereas communities define sets of nodes with more connections inside the set than outside. Roles based on structural similarity and communities based on proximity are fundamentally different but important complementary notions. Recently, the notion of structural roles has become increasingly important and has gained a lot of attention due to the proliferation of work on learning representations (node/edge embeddings) from graphs that preserve the notion of roles. Unfortunately, recent work has sometimes confused the notion of structural roles and communities (based on proximity) leading to misleading or incorrect claims about the capabilities of network embedding methods. As such, this paper seeks to clarify the misconceptions and key differences between structural roles and communities, and formalize the general mechanisms (e.g., random walks, feature diffusion) that give rise to community or role-based structural embeddings. We theoretically prove that embedding methods based on these mechanisms result in either community or role-based structural embeddings. These mechanisms are typically easy to identify and can help researchers quickly determine whether a method preserves community or role-based embeddings. Furthermore, they also serve as a basis for developing new and improved methods for community or role-based structural embeddings. Finally, we analyze and discuss applications and data characteristics where community or role-based embeddings are most appropriate.

Figures

Figures reproduced from arXiv: 1908.08572 by the authors.

**Figure 2.** Feature diffusion example via D −1A in a barbell graph (top) and a graph following the Block Chung-Lu model (bottom). For demonstration/visualization purposes, we use a single feature, the value of which is denoted by the node color. Feature values were drawn from the uniform distribution on the open interval (0, 1). For the Block Chung-Lu model, the graph was generated with exp(1.7). See text for discussion. This o… view at source ↗

**Figure 3.** All 9 graphlets and 15 node orbits with {2, 3, 4}-nodes. Each unique node position of a graphlet is labeled, e.g., nodes in the 4-star graphlet (H5) have two unique positions, namely, the star-center (hub) position or the star-edge (peripheral) position. Representative approaches falling into this category are as follows. Role2vec [Ahmed et al. 2018] proposed an end-to-end inductive framework to learn role embedding… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Graphlet/motif graphs differ in structure [PITH_FULL_IMAGE:figures/full_fig_p023_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

3 extracted references · 1 canonical work pages

[2017]

arXiv:1707.05005 (2017)

graph2vec: Learning distributed representations of graphs. arXiv:1707.05005 (2017). J. Neville, O. Şimşek, and D. Jensen. 2004. Autocorrelation and Relational Learning: Challenges and Opportunities. In Proceedings of the Workshop on Statistical Relational Learning . Jennifer Neville and David Jensen. 2000. Iterative classification in relational data. In A...

arXiv 2017
[2018]

CONE-Align: Consistent Network Alignment with Proximity-Preserving Node Embedding

Learning Role-based Graph Embeddings. In IJCAI. Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, and Eric P. Xing. 2008. Mixed Membership Stochastic Blockmodels. Journal of Machine Learning Research 9 (2008), 1981–2014. Issue Sep. Leman Akoglu, Hanghang Tong, and Danai Koutra. 2015. Graph based anomaly detection and description: a survey. DMKD 29, ...

work page Pith review arXiv 2008
[2020]

In The Thirteenth ACM International Conference on Web Search and Data Mining, James Caverlee, Xia (Ben) Hu, Mounia Lalmas, and Wei Wang (Eds.)

Toward Activity Discovery in the Personal Web. In The Thirteenth ACM International Conference on Web Search and Data Mining, James Caverlee, Xia (Ben) Hu, Mounia Lalmas, and Wei Wang (Eds.). 492–500. Lee Douglas Sailer. 1978. Structural equivalence: Meaning and definition, computation and application. Social Networks 1, 1 (1978), 73–90. Badrul M. Sarwar, ...

arXiv 1978

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [2017]

arXiv:1707.05005 (2017)

graph2vec: Learning distributed representations of graphs. arXiv:1707.05005 (2017). J. Neville, O. Şimşek, and D. Jensen. 2004. Autocorrelation and Relational Learning: Challenges and Opportunities. In Proceedings of the Workshop on Statistical Relational Learning . Jennifer Neville and David Jensen. 2000. Iterative classification in relational data. In A...

arXiv 2017

[2] [2018]

CONE-Align: Consistent Network Alignment with Proximity-Preserving Node Embedding

Learning Role-based Graph Embeddings. In IJCAI. Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, and Eric P. Xing. 2008. Mixed Membership Stochastic Blockmodels. Journal of Machine Learning Research 9 (2008), 1981–2014. Issue Sep. Leman Akoglu, Hanghang Tong, and Danai Koutra. 2015. Graph based anomaly detection and description: a survey. DMKD 29, ...

work page Pith review arXiv 2008

[3] [2020]

In The Thirteenth ACM International Conference on Web Search and Data Mining, James Caverlee, Xia (Ben) Hu, Mounia Lalmas, and Wei Wang (Eds.)

Toward Activity Discovery in the Personal Web. In The Thirteenth ACM International Conference on Web Search and Data Mining, James Caverlee, Xia (Ben) Hu, Mounia Lalmas, and Wei Wang (Eds.). 492–500. Lee Douglas Sailer. 1978. Structural equivalence: Meaning and definition, computation and application. Social Networks 1, 1 (1978), 73–90. Badrul M. Sarwar, ...

arXiv 1978