Neighborhood multiset

1 Neighborhoods and multisets in discrete mathematics

1.1 Sets, relations, and adjacency as discrete primitives

In discrete mathematics, a “neighbor” is typically defined through a relation: two objects are adjacent when they satisfy some relation predicate. In the simplest setting, adjacency is treated as a set membership question—either an element is a neighbor or it is not. This set-based viewpoint underlies many standard graph notions.

However, many combinatorial and algorithmic settings naturally produce repeated contributions to adjacency. Examples include multiedges, rule-based generation of neighbor occurrences, or situations where different adjacency channels between the same pair of elements contribute separately. A structure that keeps only presence/absence cannot represent these multiplicities faithfully.

1.2 Multisets: definition, notation, and basic operations

A multiset generalizes a set by allowing each element to appear with a nonnegative integer multiplicity. When the underlying universe is fixed, a multiset can be represented by a function that assigns each possible element a multiplicity. Common operations mirror set operations but use multiplicities: addition (sum of multiplicities), subtraction (difference with flooring at zero), and comparison notions that depend on whether one multiset has at least as many copies of each element as another.

This frequency-aware perspective is essential when “how many times” an element arises matters for counting, classification, or refinement.

1.3 From neighborhoods to neighborhood multisets

A neighborhood typically lists the adjacent objects of a node. If adjacency is simple and unique, the neighborhood can be treated as a set. When adjacency has multiplicity—such as multiple edges between the same pair—each adjacent node can appear more than once in the neighborhood description. The resulting object is a neighborhood multiset: it records each neighbor and its multiplicity.

This approach is also useful beyond graphs, for instance when a “neighbor” is generated by several independent rules or when incidences contribute repeated counts.

1.4 Multiplicity semantics and counting intuition

Multiplicity can be interpreted in several consistent ways. One common meaning is “number of distinct adjacency channels,” such as the count of parallel edges connecting two vertices. Another is “number of ways a rule produces the neighbor,” such as different paths of length one under a particular labeled incidence scheme. In both interpretations, the multiplicity is a counting weight tied to the underlying model.

Neighborhood multisets therefore support counting-based reasoning: two nodes can have identical neighbor sets but different multiplicities, leading to different combinatorial behavior in algorithms.

2 Formal definition of neighborhood multiset

2.1 Graph models and relation models

2.1.1 Simple graphs vs. multigraphs

In a simple graph, a vertex pair has at most one edge, so the neighborhood of a vertex naturally has no repeats. In a multigraph, multiple edges may connect the same pair of vertices, so the neighborhood can have repeated occurrences of the same neighbor when multiplicities are induced by edge counts.

Neighborhood multiset formalization makes this distinction explicit: the multiset multiplicity is derived from the model’s adjacency multiplicity rather than from the set of distinct neighbors alone.

2.1.2 General relations and incidence multiplicities

More generally than graphs, one can model “adjacency” as a relation that may carry multiplicity information. For instance, an incidence structure might allow several independent reasons for two elements to be considered neighbors. Formally, this can be captured by an incidence multiplicity function that counts how many adjacency units link a center element to a target element.

This yields a unified view: the neighborhood multiset of a center element is determined by how many adjacency units relate the center to each possible target.

2.2 Definition via multiplicity functions

2.2.1 Vertex-centered neighborhood multiset

Let \(V\) be a vertex set. Consider a multiplicity function \(m: V \times V \to \mathbb{N}\) where \(m(u,v)\) denotes the number of adjacency units from \(u\) to \(v\). The vertex-centered neighborhood multiset of \(u\) is then the multiset \(N(u)\) over \(V\) where the multiplicity of \(v\) equals \(m(u,v)\).

Equivalently, \(N(u)\) is the multiset whose support consists of all \(v\) with \(m(u,v)>0\), and whose total size counts \(\sum_{v \in V} m(u,v)\).

2.2.2 Edge-centered and rule-based neighborhood multisets

Some applications center neighborhood definitions at other objects than vertices. For an edge-centered neighborhood, one may define a multiset over vertices that counts endpoints with multiplicities determined by incidence structure. For rule-based neighborhood multisets, the multiplicity can represent the number of times a rule application yields a neighbor, or the total contribution of several local generators.

In all cases, the definition follows the same pattern: choose the “center” object, define the multiplicity of each “target” object, and treat those multiplicities as the multiset weights.

2.3 Notation and common conventions

2.3.1 Support vs. full multiset

It is often convenient to separate the support (the set of targets that appear at least once) from the full multiset (which includes multiplicities). The support is analogous to the conventional neighborhood in simple graph theory. The full multiset is required when parallel relations, multi-incidences, or multiple generating contributions must be preserved.

2.3.2 Cardinality and total neighbor count

The multiset cardinality of \(N(u)\), typically written \(	N(u)	\), is the total multiplicity over all targets:

N(u)	= \sum_{v} m(u,v).

\] This number generalizes degree: in undirected multigraphs, the sum of incident edge multiplicities determines the total neighbor count, though symmetry assumptions may vary by model.

3 Neighborhood constructions and variations

3.1 Open neighborhood vs. closed neighborhood

The open neighborhood typically excludes the center itself, meaning the multiplicity of \(u\) in \(N(u)\) is taken as zero unless self-adjacency is explicitly modeled. A closed neighborhood includes the center as an additional neighbor with a specified multiplicity (often exactly one in set-based settings). In multiset settings, the closed variant can be defined by adding one copy of the center to the open neighborhood multiset, or by incorporating self-incidence multiplicities if the model already includes them.

3.2 Weighted/multiplicity-driven neighborhoods

When multiplicities come from weights rather than integer counts, one can still represent a “multiset-like” neighborhood by treating weights as generalized multiplicities. In many discrete contexts the weights are restricted to nonnegative integers, aligning directly with multiset definitions. In others, weights are handled via frequency measures, but the neighborhood multiset framing remains the conceptual foundation.

3.3 Distance-k neighborhoods as multisets

A distance-\(k\) neighborhood can be defined by collecting elements at graph distance exactly \(k\) or at most \(k\). In multigraphs or in relation systems with multiplicity, there can be multiple distinct ways to realize length-\(k\) adjacency connections, each contributing multiplicity. The distance-\(k\) neighborhood multiset can therefore count not only which vertices are reachable within distance \(k\), but also how frequently they arise through length-\(k\) adjacency chains under the chosen rules.

3.4 Directed graphs and asymmetric neighborhood multisets

In directed settings, multiplicity may differ by direction. A multiplicity function \(m(u,v)\) distinguishes outgoing from incoming adjacency. One may define separate out-neighborhood and in-neighborhood multisets by restricting the center-to-target orientation. Asymmetry then becomes intrinsic: two vertices can have the same underlying undirected neighbor set but different directed multiplicity profiles.

3.5 Hypergraphs and multi-incidence neighborhoods

Hypergraphs replace edges as sets of vertices. A multi-incidence neighborhood multiset can be defined relative to hyperedge participation: a vertex may be counted multiple times due to membership in multiple hyperedges, and additional multiplicities can come from repeated hyperedge instances or weighted hyperedge contributions. The resulting neighborhood multiset records vertex-to-vertex relations induced by shared hyperedges, potentially with multiplicity reflecting how many such shared instances occur.

4 Algebra and invariants based on neighborhood multisets

4.1 Multiset aggregation and comparison

4.1.1 Inclusion, containment, and multiset difference

Given two multisets \(A\) and \(B\) on the same universe, containment is expressed by multiplicity comparisons: \(A\subseteq B\) if every element’s multiplicity in \(A\) is at most its multiplicity in \(B\). Multiset difference is computed elementwise by subtracting multiplicities, typically clamping at zero to preserve nonnegativity. These operations enable algebraic manipulation of neighborhood multisets, including iterative refinement steps.

4.1.2 Equality and multiset isomorphism concepts

Equality of neighborhood multisets means matching multiplicities for every possible neighbor target. In broader contexts, one sometimes considers isomorphism up to relabeling: two neighborhood multiset structures are “the same” if there exists a bijection between vertices that preserves multiplicity patterns. Such isomorphism notions underpin canonical labeling intuitions and symmetry-aware comparisons.

4.2 Neighborhood-based counting invariants

Neighborhood multisets can serve as invariants: if an algorithm or structural comparison preserves adjacency multiplicities, then the induced neighborhood multiset signatures remain unchanged. Counting invariants may use total neighbor counts, sums of functions of multiplicities, or more elaborate multiset polynomial evaluations that capture frequency distributions of neighbors.

Unlike set-based invariants, which only react to presence or absence, multiset-based invariants can distinguish structures that share the same support but differ in multiplicity.

4.3 Canonical signatures from neighborhood multiplicities

A canonical signature is a representation derived from a neighborhood multiset, often by sorting neighbors with their multiplicities or by hashing a frequency vector. The goal is to convert the multiset into a stable form for comparison. In practice, signatures may combine local multiplicity data with aggregated neighbor-of-neighbor information.

These signatures are especially relevant when multiplicities arise from edge multiplicities or from multiple adjacency channels, since the signature directly reflects those sources.

Many graph refinement methods iteratively aggregate neighbor information. When that information is represented as a multiset, each refinement step can be defined by combining the current labels of neighbors with the multiplicity weights that describe how many times each neighbor contributes. Stabilization occurs when further refinement stops producing new label distinctions. Neighborhood multisets provide the combinatorial mechanism that makes frequency-sensitive refinement well-defined.

5 Computation and complexity considerations

5.1 Efficient construction in different graph representations

Neighborhood multiset construction depends on representation. In adjacency-list representations of multigraphs, multiplicities can be stored as repeated neighbor entries or as aggregated counts per neighbor. In adjacency-matrix-like representations, multiplicities are directly available in matrix entries. Efficient construction aims to avoid enumerating every repeated incidence when counts are large, instead using aggregated forms where possible.

5.2 Data structures for multiset neighborhoods

A neighborhood multiset can be stored as:

a map from neighbor ID to multiplicity (sparse representation),
an array or vector of multiplicities (dense representation),
or a compressed multiset encoding such as run-length formats when multiplicities have regular structure.

Which structure is best depends on vertex count, expected sparsity, and the arithmetic operations needed later.

5.3 Complexity for neighborhood-k expansion

Distance-\(k\) neighborhood multisets may require repeated expansion of adjacency relations. With multiplicities, the number of contributing walks of length \(k\) can grow rapidly, making direct counting expensive. Complexity analysis typically depends on branching factors, sparsity, and whether the method counts distinct vertices only or aggregates multiplicities across paths.

Approaches that work with aggregated multiplicity distributions can sometimes reduce overhead compared with explicitly enumerating all length-\(k\) walks, but worst-case growth remains significant.

5.4 Practical constraints: memory and large multiplicities

Storing full multiplicity vectors can become memory intensive for large graphs. Additionally, multiplicities can exceed small integer ranges in dense or highly repetitive structures, requiring careful choice of numeric types. Practical implementations often balance exactness with compression or cap multiplicities when the downstream goal is qualitative comparison rather than exact counting.

6 Applications and motivations

Graph algorithms frequently rely on local neighborhood information to guide global decisions. Multiplicity-aware neighborhoods allow refinement methods to treat multiple adjacency channels as distinct contributions rather than collapsing them into a single presence/absence outcome. This can improve discrimination between vertices in graphs where parallel relations carry meaningful structure.

6.2 Pattern matching with frequency-sensitive neighborhoods

Pattern matching can be sensitive to frequency. If a candidate match must respect not only which vertices are adjacent but how many parallel incidences exist, neighborhood multisets provide a natural compatibility criterion. Comparing multiset signatures can quickly filter candidates, followed by more detailed verification steps.

6.3 Canonical labeling intuition (informal overview)

Canonical labeling methods often attempt to produce a stable identifier for vertices or structures derived from iterative neighborhood information. When multiplicity is present, canonicalization benefits from using multiset-aware aggregation: vertices that look similar under set-based views may still be distinguishable via their multiplicity patterns. Neighborhood multiset signatures thus help define refinement steps that are sensitive to edge multiplicity and repeated incidence patterns.

6.4 Counting problems and combinatorial enumeration

Many enumeration tasks depend on how frequently certain adjacencies occur, particularly in multigraph models and incidence-rich combinatorial structures. Neighborhood multisets offer a compact local summary that can be composed with counting frameworks. For example, local multiplicity distributions may influence counts of substructures, walks, or constrained configurations.

7 Examples and worked mini-cases

7.1 Small multigraph example with repeated neighbors

Consider a multigraph with vertices \(\{a,b,c\}\). Suppose vertex \(a\) has two parallel edges to \(b\) and one edge to \(c\), with no self-loop at \(a\). The multiplicity function yields \(m(a,b)=2\) and \(m(a,c)=1\). Then the neighborhood multiset is: \[ N(a) = \{b,b,c\}. \] Its support is \(\{b,c\}\), but its cardinality is \(3\). A vertex \(a'\) connected once to \(b\) and twice to \(c\) would have the same support yet a different neighborhood multiset, showing how multiplicities affect comparisons.

7.2 Directed example illustrating asymmetric multiplicities

In a directed multigraph, let \(u\) have three outgoing arcs to \(v\) and one outgoing arc to \(w\), while it has one incoming arc from \(v\) and no incoming arcs from \(w\). The out-neighborhood multiset is: \[ N^{out}(u)=\{v,v,v,w\}, \] and the in-neighborhood multiset is: \[ N^{in}(u)=\{v\}. \] Thus, the “neighbors” depend on direction, and the two neighborhood multisets differ even though they share some underlying vertex names.

7.3 Distance-2 neighborhood multiset example

Suppose the underlying directed structure permits multiple distinct length-2 walks from \(x\) to a target \(t\). If there are four distinct length-2 adjacency units from \(x\) to \(t\), and two distinct length-2 units from \(x\) to \(s\), then a distance-2 neighborhood multiset could be: \[ N_2(x)=\{t,t,t,t,s,s\}. \] Even if \(s\) and \(t\) are both reachable within distance 2, the multiplicity reveals how many length-2 contributions exist, which can be used in refinement or matching.

7.4 Multiset comparison example with same support, different multiplicities

Let two vertices \(p\) and \(q\) have neighbors from the set \(\{r,s\}\). For \(p\), assume multiplicities are \(m(p,r)=1\) and \(m(p,s)=3\), so \(N(p)=\{r,s,s,s\}\). For \(q\), assume \(m(q,r)=2\) and \(m(q,s)=2\), so \(N(q)=\{r,r,s,s\}\). Both neighborhoods have the same support size, but their multisets are different because multiplicity distributions differ. Any algorithm that relies on neighborhood multiset equality can distinguish \(p\) and \(q\).

8.1 Degree sequences and generalized degree notions

In simple graphs, degrees determine neighbor counts. With multiplicity, the total neighbor multiset cardinality generalizes degree by counting adjacency units. This leads to generalized degree sequences that reflect parallel edges, self-incidences, or directed multiplicity contributions, depending on the neighborhood multiset definition used.

8.2 Multiset polynomials and generating functions (high level)

A neighborhood multiset can be encoded into polynomial forms that track multiplicities of neighbors via exponents or coefficients. Such encodings enable generating-function techniques and algebraic manipulations. At a high level, these representations transform local frequency data into a format suitable for counting arguments and combinatorial identities.

8.3 Multigraph adjacency matrices and multiplicity encoding

For multigraphs, an adjacency matrix can store multiplicities directly: the entry in row \(u\), column \(v\) can equal \(m(u,v)\). The neighborhood multiset of \(u\) corresponds to the row of multiplicities viewed as a multiset over the vertex universe. This links neighborhood multiset operations to linear-algebraic computations over multigraph adjacency structures.

Neighborhood refinement methods inspired by the Weisfeiler–Lehman paradigm iteratively label vertices based on neighbor multisets. In multiset-aware variants, the aggregation includes multiplicities, so parallel adjacency influences the refinement outcome. Conceptually, neighborhood multisets provide the formal object that these refinement schemes aggregate at each iteration.